Pagini recente » Borderou de evaluare (job #1104611) | Cod sursa (job #2307523) | Cod sursa (job #3038956) | Borderou de evaluare (job #1907632) | Cod sursa (job #975473)
Cod sursa(job #975473)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#include <string>
#define LE 1000666
string A,B;
int L,R,i,j,prfx[LE*2],st;
int pos_prfx;
int result,res[LE];
int main() {
f>>A>>B;
L=R=-1;
int ni=A.length();
A+=B;
int N1=A.length();
for(i=1; i<N1; ++i) {
if (A[i]!=A[0]) continue;
if (R<=i) st=i+1;
else {
pos_prfx=i-L;
if (prfx[pos_prfx]>=R-i+1) st=R+1;
else {
prfx[i]=prfx[pos_prfx];
continue;
}
}
for(j=st; j<=i+ni; ++j)
if (j==i+ni||A[j]!=A[j-i]) {
prfx[i]=j-i;
--j;
break;
}
if (j>R) R=j,L=i;
}
for(i=ni; i<=N1; ++i) {
if (prfx[i]==ni) {
++result;
if (result<=1000) res[result]=i-ni;
}
}
g<<result<<'\n';
for(i=1; i<=min(1000,result); ++i)
g<<res[i]<<" ";
//for(i=0; i<N1; ++i) cout<<prfx[i];
// cout<<'\n';
//cout<<A<<'\n';
f.close();
g.close();
return 0;
}