Submission #1076535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076535		vjudge1	Necklace (Subtask 4) (BOI19_necklace4)	C++17	3 / 15	850 ms	1104 KiB

necklace

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

const int N = 6003;

string s, t;
int pi[2][N], knuth[2][N];
int ans = 0;
pair<int, int> kq;

void kmp(string &s, string &t, int x)
{
    string tmp = s + '0' + t;
    int n = tmp.size();
    for (int i = 1; i < n; i++)
    {
        int j = pi[x][i - 1];
        while (j > 0 && tmp[i] != tmp[j])
            j = pi[x][j - 1];
        if (tmp[i] == tmp[j])
            j++;
        pi[x][i] = j;
        if(i > s.size())
            knuth[x][i - s.size()] = j;//, cout << j << " ";
    }
//    cout << tmp << '\n';
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> s >> t;
    for(int i = 0; i < s.size(); i++)
    {
        string tmp = "";
        for(int j = i; j < s.size(); j++)
            tmp = tmp + s[j];
        kmp(tmp, t, 0);
        tmp = "";
        reverse(t.begin(), t.end());
        for(int j = i - 1; j >= 0; j--)
            tmp = tmp + s[j];
        kmp(tmp, t, 1);
        reverse(t.begin(), t.end());
        for(int j = 1; j <= t.size(); j++)
        {
            int rev = t.size() - j + 1;
            if(ans < knuth[0][j] + knuth[1][rev - 1 ])
            {
                ans = knuth[0][j] + knuth[1][rev - 1];
                kq.fi = i - knuth[1][rev - 1];
                kq.se = j - knuth[0][j];
            }
        }
    }
//    reverse(t.begin(), t.end());
//    for(int i = 0; i < s.size(); i++)
//    {
//        string tmp = "";
//        for(int j = i; j < s.size(); j++)
//            tmp = tmp + s[j];
//        kmp(tmp, t, 0);
//        tmp = "";
//        reverse(t.begin(), t.end());
//        for(int j = i - 1; j >= 0; j--)
//            tmp = tmp + s[j];
//        kmp(tmp, t, 1);
//        reverse(t.begin(), t.end());
//        for(int j = 1; j <= t.size(); j++)
//        {
//            int rev = t.size() - j + 1;
//            if(ans < knuth[0][j] + knuth[1][rev - 1])
//            {
//                ans = knuth[0][j] + knuth[1][rev - 1];
//                kq.fi = i - knuth[1][rev - 1];
//                kq.se = t.size() - (j + knuth[1][rev - 1]);
//            }
//        }
//    }
    cout << ans << '\n';
    cout << kq.fi << " " << kq.se;
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void kmp(std::string&, std::string&, int)':
necklace.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if(i > s.size())
      |            ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
necklace.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j = i; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:50:26: 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 j = 1; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~

• Subtask 1: 3 / 15