Pagini recente » Cod sursa (job #1626746) | Cod sursa (job #2796057) | Cod sursa (job #2902590) | Cod sursa (job #148436) | Cod sursa (job #972492)
Cod sursa(job #972492)
#define NMax 2000005
#include <fstream>
#include<cstring>
#include<algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[NMax],B[NMax];int N,M,P[NMax],Nr,Sol[1002];
void Read()
{
fin>>(A+1)>>(B+1);
fout<<(A+1)<<'\n'<<(B+1);
M=strlen(A+1);
N=strlen(B+1);
}
void Build_Prefixes()
{
int i,q;
P[1]=0;
for(q=0,i=2;i<=M;i++)
{
while(q&&A[q+1]!=A[i])
q=P[q];
if(A[q+1]==A[i])
q++;
P[i]=q;
}
}
void KMP()
{
int i,q=0;
for(i=1;i<=N;i++)
{
while(q&&A[q+1]!=B[i])
q=P[q];
if(A[q+1]==B[i])
q++;
if(q==M)
{
Nr++;
if(Nr<=1000)
Sol[Nr]=i-M;
}
}
}
void Print()
{
int i;
fout<<Nr<<"\n";
for(i=1;i<=min(Nr,1000);i++)
fout<<Sol[i]<<" ";
fout<<"\n";
}
int main()
{
Read();
Build_Prefixes();
KMP();
Print();
return 0;
}