oj.uz

Submission #376897

# Submission time Handle Problem Language Result Execution time Memory
376897 2021-03-12T06:34:48 Z Noran Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 1 ms 364 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define all(x) x.begin(),x.end()
#define fast_io ios_base::sync_with_stdio(false), cin.tie(), cout.tie();

const int maxn = 5e3 + 7;

string s, t, trev;
int ans;

int kmp1[maxn], kmp2[maxn];
int match[maxn];

void KMP(string &s, string &t, int kmp[maxn])
{
    match[1] = 0;
    for(int i = 2; i <= s.size(); i++)
    {
        int tmp = match[i - 2];
        while(tmp && s[tmp] != s[i - 1])
            tmp = match[tmp];

        if(s[tmp] == s[i - 1])
            tmp++;

        match[i] = tmp;
    }

    int tmp = 0;
    for(int i = 1; i <= t.size(); i++)
    {
        while(tmp && s[tmp] != t[i - 1])
            tmp = match[tmp];

        if(s[tmp] == t[i - 1])
            tmp++;

        kmp[i - 1] = tmp;
    }
}

void solve(int revFlag)
{
    if(revFlag)
        swap(t, trev);

    for(int i = 0; i <= s.size(); i++)
    {
        string s1, s2;

        s1 = s.substr(0, i); reverse(all(s1));
        s2 = s.substr(i, s.size() - i);

        KMP(s1, trev, kmp1);
        KMP(s2, t, kmp2);

        for(int j = 0; j <= t.size(); j++)
        {
            int p1, p2; p1 = p2 = 0;

            if(j > 0) p1 = kmp2[j - 1];
            if(j < t.size()) p2 = kmp1[t.size() - j - 1];

            int tmp = p1 + p2;
            ans = max(ans, tmp);
        }
    }
}

int32_t main()
{
    fast_io;

    cin >> s >> t;
    trev = t; reverse(all(trev));

    solve(0); solve(1);
  
    cout << ans << "\n";

    return 0;
}

Compilation message

necklace.cpp: In function 'void KMP(std::string&, std::string&, int*)':
necklace.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 2; i <= s.size(); i++)
      |                    ~~^~~~~~~~~~~
necklace.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 1; i <= t.size(); i++)
      |                    ~~^~~~~~~~~~~
necklace.cpp: In function 'void solve(int)':
necklace.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i <= s.size(); i++)
      |                    ~~^~~~~~~~~~~
necklace.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j = 0; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~
necklace.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if(j < t.size()) p2 = kmp1[t.size() - j - 1];
      |                ~~^~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -