Submission #376897

#	Time	Username	Problem	Language	Result	Execution time	Memory
376897		Noran	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	0 / 85	1 ms	364 KiB

necklace

#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 (stderr)

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 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40