|
|
вернуться в форумhelp please, I used KMP but I have TLE_5 #include <iostream> #include <string> using namespace std; long p[260000],x,i,j,k,d,l; char t[260000],s[510000]; void prefix() {
p[0]=0;k=0; for (i=1;i<x;i++) { while ((k>0)&&(t[k]!=t[i])) k=p[k];
if (t[k]==t[i]) k++; p[i]=k;
}
} void solve() { k=0;d=0; for (i=0;i<2*x;i++) { while ((k>0)&&(t[k]!=s[i])) k=p[k]; if (s[i]==t[k]) k++; if (k>=x) {d=1;break;} } l=2*x-i-1; if (l==x) l=0; if (d==0) cout<<-1<<endl; else cout<<l<<endl; } int main() {long l; freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); cin>>x; cin.get(); for (i=1;i<=x;i++) p[i]=0; gets(s); l=strlen(s); gets(t);
strncat(s,s,l); l=strlen(s); prefix();
solve(); fclose(stdin); fclose(stdout); return 0; } what is wrong here? at last got AC my mistake was: k=p[k] should be k=p[k-1] Re: at last got AC Послано MIM 4 мар 2012 04:14 Giorgi,you a good man))Thank you!My mistake also there)) |
|
|