Pagini recente » Monitorul de evaluare | Cod sursa (job #1805142) | Cod sursa (job #1936838) | Cod sursa (job #1575650) | Cod sursa (job #161351)
Cod sursa(job #161351)
#include <iostream>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define NMAX 2000001
char P[NMAX],T[NMAX];
int Pi[NMAX],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) T[i-p+1]=0,r++;
}
}
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;
for ( i=0 ; i<r-1 ; i++ )
{
while (T[p]) p++;
printf ( "%d " , p );
p++;
}
if (r)
{
while (T[p]) p++;
printf ( "%d\n" , p );
}
fclose ( stdout );
return 0;
}