Pagini recente » Cod sursa (job #293541) | Cod sursa (job #1687257) | Cod sursa (job #1476063) | Cod sursa (job #1697689) | Cod sursa (job #307239)
Cod sursa(job #307239)
#include<fstream>
#include<cstring>
#define MaxL 2000005
#define Min(a,b) ((a<b)?a:b)
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[MaxL],B[MaxL];
int N,M,i,phi[MaxL],pos[1005],n;
void prefix()
{ int i,q=0;
for(i=2,phi[1]=0;i<=M;i++)
{ while(q&&A[q+1]!=A[i])
q=phi[q];
if(A[q+1]==A[i]) q++;
phi[i]=q;
}
}
void KMP()
{ int i,q=0;
for(i=1;i<=N;i++)
{ while(q&&A[q+1]!=B[i])
q=phi[q];
if(A[q+1]==B[i])
q++;
if(q==M)
{ q=phi[M];
n++;
if(n<=1000)
pos[n]=i-M;
}
}
}
void print()
{ fout<<n<<'\n';
for(i=1;i<=Min(n,1000);i++)
fout<<pos[i]<<' ';
}
int main()
{ fin.getline(A,MaxL);
fin.getline(B,MaxL);
N=strlen(B);
M=strlen(A);
for(i=M+1;i>0;--i)
A[i]=A[i-1];
A[0]=' ';
for(i=N+1;i>0;--i)
B[i]=B[i-1];
B[0]=' ';
prefix();
KMP();
print();
return 0;
}