Pagini recente » Cod sursa (job #1198225) | Cod sursa (job #1161909) | Cod sursa (job #2105773) | Cod sursa (job #2360980) | Cod sursa (job #2700285)
#include <bits/stdc++.h>
#define LMAX 2000002
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[LMAX], B[LMAX];
char C[LMAX+LMAX];
int Z[LMAX+LMAX],cnt;
int main()
{
in.getline(A,LMAX);
in.getline(B,LMAX);
int n=strlen(A),m=strlen(B);
if(n>m)
{
cout<<"0";
return 0;
}
strcpy(C,A);
strcat(C,"+");
strcat(C,B);
int L=0,R=0;
for(int i=1;i<n+m+1;i++)
{
if(i>R)
{
L=i;
R=i;
while(R<n+m+1 && C[R]==C[R-i])
R++;
R--;
Z[i]=R-L+1;
}
else
{
int k=i-L;
if(R-i+1>Z[k])
Z[i]=Z[k];
else
{
L=i;
while(R<n+m+1 && C[R]==C[R-i])
R++;
R--;
Z[i]=R-L+1;
}
}
if(Z[i]==n)
cnt++;
}
out<<cnt<<'\n';
int ok=1;
for(int i=n+1;i<n+m+1 && ok<=1000;i++)
if(Z[i]==n){
out<<i-n-1<<' ';
ok++;
}
return 0;
}