Pagini recente » Cod sursa (job #257521) | Cod sursa (job #249016) | Cod sursa (job #763002) | Cod sursa (job #2692015) | Cod sursa (job #978322)
Cod sursa(job #978322)
#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;
}
}
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);
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[i];
}
if(A[t] == B[i]){
t++;
}
if(t == N){
t = pi[t-1];
if(dim < 1000){
sol[dim] = i - N + 1;
}
dim++;
}
}
fprintf(pg, "%d\n", dim);
for(i = 0; i < dim && i < 1000; i++)
fprintf(pg, "%d ", sol[i]);
fclose(pf);
fclose(pg);
return 0;
}