Pagini recente » Cod sursa (job #485925) | Cod sursa (job #1547224) | Rating cont de incercari (Vlad_Robert) | Cod sursa (job #2496556) | Cod sursa (job #1912367)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000001],B[2000001];
int Ap[2000001];
int v[1002];
int main(){
int la,lb,i,j;
bool b;
fin.get(A,2000000);
fin.get();
fin.get(B,2000000);
la=strlen(A);
lb=strlen(B);
j=0;
for(i=1;i<la;i++){
if(A[i]==A[j]){Ap[i]=j+1;++j;}
else
while(j){
j=Ap[j-1];
}
}
j=0;
for(i=0;i<lb;i++){
if(A[j]==B[i])++j;
else if(j){j=Ap[j-1];i--;}
if(j==la){
++v[0];
if(v[0]<=1000)v[v[0]]=i+1-j;
j=Ap[j-1];
i--;
}
}
/*
for(i=0;i<lb+1-la;i++){
if(lb<la)break;
b=true;
for(j=0;j<la;j++)
if(A[j]!=B[i+j]){b=false;break;}
if(b)
if(v[0]<1000)v[++v[0]]=i;
else v[0]++;
}
*/
fout<<v[0]<<'\n';
for(i=1;i<=min(v[0],1000);i++)
fout<<v[i]<<" ";
fout<<'\n';
fin.close();
fout.close();
return 0;
}