Pagini recente » Cod sursa (job #1917774) | Cod sursa (job #1923600) | Cod sursa (job #611363) | Cod sursa (job #1677371) | Cod sursa (job #1201230)
//KMP
#include <stdio.h>
#define MAXL 2000000
#define MAXOUT 1000
char A[MAXL + 1], B[MAXL + 1];
int rez[MAXL], dr = 0;
int nxt[MAXL];
int getlen(char *c){
int rez = 0;
while(c[rez] != '\n') rez++;
return rez;
}
void prefix(int n){
int i, k;
k = -1;
nxt[0] = -1;
for(i = 1; i < n; i++){
while(k > -1 && A[k + 1] != A[i]){
k = nxt[k];
}
if(A[k + 1] == A[i]) k++;
nxt[i] = k;
}
return ;
}
void kmp(int a, int b){
int i, k;
k = -1;
for(i = 0; i < b; i++){
while(k > -1 && A[k + 1] != B[i]){
k = nxt[k];
}
if(A[k + 1] == B[i]) k++;
if(k == a - 1){
rez[dr] = i - a + 1;
dr++;
}
}
return ;
}
int main()
{
FILE *in = fopen("strmatch.in", "r");
int a, b;
fgets(A, MAXL + 1, in);
fgets(B, MAXL + 1, in);
fclose(in);
a = getlen(A);
b = getlen(B);
prefix(a);
kmp(a, b);
FILE *out = fopen("strmatch.out", "w");
int i;
fprintf(out, "%d\n", dr);
for(i = 0; i < dr && i < MAXOUT; i++){
fprintf(out, "%d ", rez[i]);
}
fclose(out);
return 0;
}