Pagini recente » Cod sursa (job #1332150) | Cod sursa (job #1438782) | Cod sursa (job #2192594) | Cod sursa (job #1337960) | Cod sursa (job #1213457)
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
char A[NMAX],B[NMAX],C[NMAX];
int i,sol,m,n,s[NMAX],p[NMAX],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;
}