Pagini recente » Cod sursa (job #1758153) | Cod sursa (job #694447) | Cod sursa (job #1588529) | Cod sursa (job #1424031) | Cod sursa (job #584447)
Cod sursa(job #584447)
#include<stdio.h>
#include<string.h>
using namespace std;
#define dim 2000001
#define minim( a , b ) ( a < b ? a : b)
int n,m,urm[dim],nr,v[1001],x,i,k;
char T[dim],P[dim];
void urmatorul()
{
urm[0] = k = -1;
for( x = 1; x < m; x++ )
{
while( k>-1 && P[k+1] != P[x])
k = urm[k] ;
if(P[k+1]==P[x])
k++;
urm[x] = k;
}
}
int main()
{
FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");
fscanf(f,"%s", P);
fscanf(f,"%s", T);
n=strlen(T);
m=strlen(P);
urmatorul();
x=-1;
for(i=0;i<n;i++)
{
while(x>-1 && P[x+1]!=T[i])
x=urm[x];
if(P[x+1]==T[i])
x++; //s-au potrivit
if(x==m-1)
{ nr++;
if(nr<=1000)
v[nr]=i-m+1;
x=urm[x];
}
}
fprintf(g,"%d\n",nr);
for(i=1;i<=minim(nr,1000);i++)
fprintf(g,"%d ",v[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}