Pagini recente » Cod sursa (job #3189400) | Cod sursa (job #2071673) | Cod sursa (job #1455204) | Cod sursa (job #1416197) | Cod sursa (job #298133)
Cod sursa(job #298133)
#include <cstdio>
#include <string.h>
#define Nmax 2000010
int A, B, pi[Nmax], p, i, sol[Nmax];
char a[Nmax], b[Nmax];
void prefix(){
int p = 0, i;
for(i = 2; i <= A; i++){
while( p && a[p + 1] != a[i])
p = pi[p];
if( a[p + 1] == a[i] ){
p++;
pi[i] = p;
}
}
}
int main(){
FILE *f = fopen("strmatch.in", "r");
FILE *g = fopen("strmatch.out", "w");
a[0] = ' '; b[0] = ' ';
fscanf(f,"%s",a + 1);
fscanf(f,"%s",b + 1);
A = strlen(a) - 1; B = strlen(b) - 1;
prefix();
p = 1;
for(i = 1; i <= B; i++){
while( p && b[i] != a[p+1] )
p = pi[p];
if( b[i] == a[p+1] ){
p++;
if(p == A)
sol[++sol[0]] = i - p;
}
}
fprintf(g,"%d\n",sol[0]);
for(i = 1; i <= sol[0]; i++)
fprintf(g,"%d ", sol[i]);
fclose(f);
fclose(g);
return 0;
}