Submission #1196312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196312		Petrix	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	231 ms	652 KiB

necklace

#include <iostream>
#include <algorithm>
using namespace std;

string a,b;
int v[2][7001];
int p[7001];

void kmp(string s1,string s2,int poz1) {
    int i,poz;string s=s1+'#'+s2;
    for(i=1;i<=7000;i++) v[poz1][i]=0;
    for(i=1;i<s.size();i++){
        poz=p[i-1];
        while(poz>0 && s[i]!=s[poz]) poz=p[poz-1];
        if(s[i]==s[poz]) poz++;
        p[i]=poz;
        if(i>s1.size()) v[poz1][i-s1.size()]=p[i];
    }
}

int main()
{
    string s1,s2,auxs1,auxb;
    int aux,i,j,rasp=-1,raspa,raspb;
    cin>>a>>b;
    for(aux=0;aux<2;aux++){
        for(i=0;i<=a.size();i++){
            s1=a.substr(0,i);s2=a.substr(i,a.size()-i);auxs1=s1;auxb=b;
            reverse(auxs1.begin(),auxs1.end());
            reverse(auxb.begin(),auxb.end());
            kmp(auxs1,b,0);
            kmp(s2,auxb,1);
            for(j=1;j<=b.size();j++){
                if(v[0][j]+v[1][b.size()-j]>rasp){
                    rasp=v[0][j]+v[1][b.size()-j];
                    raspa=i-v[0][j];
                    if(aux) raspb=b.size()-j-v[1][b.size()-j];
                    else raspb=j-v[0][j];
                }
            }
        }
        reverse(b.begin(), b.end());
    }
    cout<<rasp<<"\n"<<raspa<<" "<<raspb;
    return 0;
}

• Subtask 1: 15 / 15