Submission #1288199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288199		LmaoLmao	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	110 ms	584 KiB

necklace

#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<int,int>;
using aa = array<int,4>;
const int N=4e5+5;
const int MOD=1e9+7;

int p[6005];
int ans[3006];

int solve(string a,string b) {
    string s=a+'.'+b;
    int res=0;
    for(int i=1;i<s.size();i++) {
        int j=p[i-1];
        while(j>0 && s[i]!=s[j]) {
            j=p[j-1];
        }
        if(s[i]==s[j]) j++;
        p[i]=j;
        res=max(res,j);
    }
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string a,b;
    cin >> a >> b;
    int res=0;
    for(int i=0;i<=a.size();i++) {
        string t1=a.substr(0,i);
        string t2=b;
        reverse(t1.begin(),t1.end());
        reverse(t2.begin(),t2.end());
        solve(t1,t2);
        for(int j=0;j<t2.size();j++) {
            ans[j+1]=p[t2.size()-j-1+t1.size()];
            //if(i==5) cout << ans[j+1] << ' ' << j+1 << endl;
        }
        t1=a.substr(i,a.size()-i);
        reverse(t2.begin(),t2.end());
        solve(t1,t2);
        for(int j=0;j<t2.size();j++) {
            ans[j+1]+=p[j+t1.size()+1];
            res=max(res,ans[j]);
            //if(i==5) cout << ans[j] << ' ' << j << endl;
        }
        for(int j=0;j<=3005;j++) {
            res=max(res,ans[j]);
            ans[j]=0;
        }

    }
    cout << res;
    return 0;
}

• Subtask 1: 0 / 15