Pagini recente » Monitorul de evaluare | Cod sursa (job #1254728) | Cod sursa (job #1254754) | Cod sursa (job #2273377) | Cod sursa (job #1174258)
#include <fstream>
#include <cstring>
using namespace std;
int i,q,nr_sol,n,m;
int sol[2000005],p[2000005];
char A[2000005],B[2000005],C[2000005];
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(B,2000005);
f.get();
f.get(A,2000005);
n=strlen(A);m=strlen(B);
strcpy(C,A);
strcpy(A+1,C);
strcpy(C,B);
strcpy(B+1,C);
p[1]=0;
for(i=2;i<=m;i++) {
q=p[i-1];
while(B[i]!=B[q+1] && q!=0)
q=p[q];
if(B[i]==B[q+1])
p[i]=q+1;
else
p[i]=0;
}
q=0;
for(i=1;i<=n;i++) {
while(A[i]!=B[q+1] && q!=0)
q=p[q];
if(A[i]==B[q+1])
q++;
if(q==m) {
nr_sol++;
sol[nr_sol]=i-m;
q=p[q];
}
}
g<<nr_sol<<"\n";
for(i=1;i<=1000 && i<=nr_sol;i++)
g<<sol[i]<<" ";
return 0;
}