Pagini recente » Cod sursa (job #895355) | Cod sursa (job #2130443) | Cod sursa (job #177389) | Cod sursa (job #1213505) | Cod sursa (job #390499)
Cod sursa(job #390499)
#include<cstdio>
#include<string.h>
#define max 2000001
char t[max],p[max];
int ant[max],n,m;
int poz[1001];
void prefix(){
int k,i;k=-1;
poz[0]=0;
for( i=1; i<m;i++){
while( k>0 && p[k+1] != p[i] ) k = ant[k];
if( p[k+1] == p[i] ) k++;
ant[i] = k;
}
}
int main(){
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
int x = -1;int k=0;
fscanf(f,"%s\n%s",p,t);
m = strlen(p);
n = strlen(t);
prefix();
int i;
for(i=0; i<n;i++){
while( x>0 && p[ x+1 ] != t[i] ) x = ant[x];
if( p[x+1] == t[i] ) x++;
if( x == m-1 ){ k++; if( k<1001 ) poz[k] = i-m+1; x = ant[x]; }
}
fprintf(g,"%d\n",k);
if( k>1000 ) k=1000;
for(i=1;i<=k;i++) fprintf(g,"%d ",poz[i]);
return 0;
}