Pagini recente » Cod sursa (job #2950531) | Cod sursa (job #754157) | Cod sursa (job #3179939) | Cod sursa (job #2890887) | Cod sursa (job #978247)
Cod sursa(job #978247)
#include<stdio.h>
#include<string.h>
#define NMAX 2000001
int sol[NMAX];
int pi[NMAX];
char A[NMAX], B[NMAX];
int dim = 0;
void read(FILE *pf){
fscanf(pf, "%s", A);
fscanf(pf, "%s", B);
}
void KMP_prefix(char A[NMAX], int N){
int k = 0, i;
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 N, int M){
int t = 0, i = 0;
while(i < M){
while(t > 0 && A[t] != B[i])
t = pi[i];
if(A[t] == B[i])
t++;
if(t == N){
sol[dim] = i - N + 1;
dim++;
i = i - N + 2;
}
else
i++;
}
}
void print(FILE *pg){
int i;
fprintf(pg, "%d\n", dim);
for(i = 0; i < dim; i++)
fprintf(pg, "%d ", sol[i]);
}
int main(){
int M, N;
FILE *pf, *pg;
pf = fopen("strmatch.in", "r");
pg = fopen("strmatch.out", "w");
read(pf);
N = sizeof(A);
M = sizeof(B);
KMP_prefix(A, N);
KMP_match(A, B, N, M);
print(pg);
fclose(pf);
fclose(pg);
return 0;
}