Pagini recente » Cod sursa (job #2036218) | Cod sursa (job #1624350) | Cod sursa (job #1954280) | Cod sursa (job #1952068) | Cod sursa (job #1159027)
#include <fstream>
#include <cstring>
using namespace std;
char A[2000005],B[2000005],C[2000005];
int i,sol,m,n,s[2000005],p[2000005],q;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>B;
f>>A;
m=strlen(B);
n=strlen(A);
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[q+1]==B[i])
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) {
sol++;
s[sol]=i-m;
q=p[q];
}
}
g<<sol<<"\n";
for(i=1;i<=sol && i<=1000;i++)
g<<s[i]<<" ";
g<<"\n";
return 0;
}