#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;
}
컴파일 시 표준 에러 (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;
| ~^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |