Pagini recente » Cod sursa (job #2438256) | Cod sursa (job #1043573) | Cod sursa (job #212126) | Cod sursa (job #1085088) | Cod sursa (job #315361)
Cod sursa(job #315361)
using namespace std;
#include <cstdio>
#include <string.h>
#include <algorithm>
#define Nmax 2000010
int A, B, pi[Nmax], p, i, sol[1024];
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 = 0;
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)
if(sol[0] <= 1000)
sol[++sol[0]] = i - p;
else
++sol[0];
}
}
fprintf(g,"%d\n",sol[0]);
int M = min(sol[0], 1000);
for(i = 1; i <= M; i++)
fprintf(g,"%d ", sol[i]);
fclose(f);
fclose(g);
return 0;
}