Pagini recente » Cod sursa (job #159857) | Cod sursa (job #2700765) | Cod sursa (job #210181) | Cod sursa (job #676082) | Cod sursa (job #161368)
Cod sursa(job #161368)
#include <iostream>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define NMAX 2000001
char P[NMAX],T[NMAX];
int Pi[NMAX],R[1000],pi,r;
void prefix(char *P, int p)
{
int k=-1;
for (Pi[0]=-1,pi=1;pi<p;pi++)
{
while (k+1 && P[k+1]!=P[pi] ) k=Pi[k];
k+=(int)(P[k+1]==P[pi]);
Pi[pi]=k;
}
}
void KMP(char *P, int p, char *T, int t)
{
int q=-1,i;
for ( i=0;i<t;i++)
{
while (q+1&&P[q+1]!=T[i]) q=Pi[q];
q+=(int)(P[q+1]==T[i]);
if (q==p-1)
{
r++;
if (r<1001) R[r-1]=i-p+1;
}
}
}
int main ()
{
int i;
fscanf (fopen (FIN,"r") , "%s\n%s\n" , P , T);
int p=strlen(P),t=strlen(T);
prefix(P,p);
KMP(P,p,T,t);
freopen (FOUT , "w" , stdout);
printf ( "%d\n" , r );p=0;if(r>1000) r=1000;
for ( p=0 ; p<r-1 ; p++ )
printf ( "%d " , R[p] );
if (r) printf ( "%d\n" , R[p] );
fclose ( stdout );
return 0;
}