Submission #1196309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196309		Petrix	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	2 ms	576 KiB

necklace

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

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

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()
{
    int aux,i,j,rasp=-1,raspa,raspb;
    cin>>a>>b;
    for(aux=0;aux<2;aux++){
        for(i=0;i<=a.size();i++){
            string s1=a.substr(0,i),s2=a.substr(i,a.size()-i);
            kmp(string(s1.rbegin(),s1.rend()),b,0);
            kmp(s2,string(b.rbegin(),b.rend()),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;
}

Compilation message (stderr)

necklace.cpp: In function 'void kmp(std::string, std::string, int)':
necklace.cpp:11:36: warning: iteration 6999 invokes undefined behavior [-Waggressive-loop-optimizations]
   11 |     for(i=1;i<=7000;i++) v[poz1][i]=0;
      |                          ~~~~~~~~~~^~
necklace.cpp:11:14: note: within this loop
   11 |     for(i=1;i<=7000;i++) v[poz1][i]=0;
      |             ~^~~~~~

• Subtask 1: 0 / 15