Pagini recente » Cod sursa (job #421400) | Cod sursa (job #135415) | Cod sursa (job #3245543) | Cod sursa (job #2062296) | Cod sursa (job #978344)
Cod sursa(job #978344)
#include<stdio.h>
#include<cstring>
#define NMAX 2000005
#define dimMAX 1000
int sol[dimMAX];
int pi[NMAX];
char A[NMAX], B[NMAX];
int dim = 0;
void KMP_prefix(char A[NMAX]){
int k = 0, i, N = strlen(A)-1;
pi[k] = 0;
for(i = 1; i < N; i++){
while(k > 0 && A[k] != A[i])
k = pi[k];
if(A[k] == A[i])
k++;
pi[i] = k;
}
}
void KMP_match(char A[NMAX], char B[NMAX]){
int i, t = 0, M = strlen(B)-1, N = strlen(A)-1;
for(i = 0; i < M; i++){
while(t > 0 && A[t] != B[i])
t = pi[t-1];
if(A[t] == B[i])
t++;
if(t == N){
t = pi[t-1];
if(dim < 1000){
sol[dim] = i - N + 1;
}
dim++;
}
}
}
int main(){
FILE *pf, *pg;
pf = fopen("strmatch.in", "r");
pg = fopen("strmatch.out", "w");
fgets(A, sizeof(A), pf);
fgets(B, sizeof(B), pf);
KMP_prefix(A);
KMP_match(A, B);
int i;
fprintf(pg, "%d\n", dim);
for(i = 0; i < dim && i < 1000; i++)
fprintf(pg, "%d ", sol[i]);
fclose(pf);
fclose(pg);
return 0;
}