Submission #1076702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076702		Namviet2704	Necklace (Subtask 4) (BOI19_necklace4)	C++17	3 / 15	1171 ms	852 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;
    }
}

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 < min((int)s.size(), 1000); 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;
//            cout << j << " " << rev << '\n';
            if(ans < knuth[0][j] + knuth[1][rev])
            {
                ans = knuth[0][j] + knuth[1][rev];
                kq.fi = i - knuth[1][rev];
                kq.se = t.size() - (j + knuth[1][rev]);
            }
        }
    }
//    for(int i = 2000; i < (int)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;
////            cout << j << " " << rev << '\n';
//            if(ans < knuth[0][j] + knuth[1][rev])
//            {
//                ans = knuth[0][j] + knuth[1][rev];
//                kq.fi = i - knuth[1][rev];
//                kq.se = t.size() - (j + knuth[1][rev]);
//            }
//        }
//    }
    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:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
necklace.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = i; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j = 1; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~
necklace.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j = i; j < s.size(); j++)
      |                        ~~^~~~~~~~~~
necklace.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int j = 1; j <= t.size(); j++)
      |                        ~~^~~~~~~~~~~

• Subtask 1: 3 / 15