Pagini recente » Cod sursa (job #574584) | Cod sursa (job #74082) | Cod sursa (job #658816) | Cod sursa (job #607820) | Cod sursa (job #1437133)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 2000005
int* prefix(char A[]);
void kmp(char B[], char A[], int v[], int* nr);
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char A[MAX], B[MAX];
int v[1005], nr = 0, i;
scanf("%s\n%s", A, B);
for(i = strlen(A); i > 0; i--)
A[i] = A[i - 1];
for(i = strlen(B); i > 0; i--)
B[i] = B[i - 1];
A[0] = ' ';
B[0] = ' ';
kmp(B, A, v, &nr);
printf("%d\n", nr);
for(i = 1; i <= nr && i <= 1000; i++)
printf("%d ", v[i]);
printf("\n");
return 0;
}
int* prefix(char A[]){
int n = strlen(A) - 1, k, q;
int* pr = malloc((n + 1) * sizeof(int));
if(!pr) return NULL;
pr[1] = 0;
k = 0;
for(q = 2; q <= n; q++){
while(k > 0 && A[k + 1] != A[q])
k = pr[k];
if(A[k + 1] == A[q])
k++;
pr[q] = k;
}
return pr;
}
void kmp(char B[], char A[], int v[], int* nr){
int n = strlen(B) - 1;
int m = strlen(A) - 1;
int* pr = prefix(A), q = 0, i;
for(i = 1; i <= n; i++){
while(q > 0 && A[q + 1] != B[i])
q = pr[q];
if(A[q + 1] == B[i])
q++;
if(q == m){
(*nr)++;
if(*nr <= 1000)
v[*nr] = i - m;
q = pr[q];
}
}
}