Pagini recente » Cod sursa (job #177405) | Cod sursa (job #531700) | Cod sursa (job #1902230) | Cod sursa (job #1729345) | Cod sursa (job #1437124)
#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 = -1, i;
scanf("%s\n%s", A, B);
kmp(B, A, v, &nr);
printf("%d\n", nr + 1);
for(i = 0; i <= nr; i++)
printf("%d ", v[i]);
printf("\n");
return 0;
}
int* prefix(char A[]){
int n = strlen(A), k, q;
int* pr = malloc(n * sizeof(int));
if(!pr) return NULL;
pr[0] = 0;
k = 0;
for(q = 1; q < n; q++){
while(k > 0 && A[k] != A[q])
k = pr[k];
if(A[k] == A[q])
k++;
pr[q] = k;
}
return pr;
}
void kmp(char B[], char A[], int v[], int* nr){
int n = strlen(B);
int m = strlen(A);
int* pr = prefix(A), q = 0, i;
for(i = 0; i < n; i++){
while(q > 0 && A[q] != B[i])
q = pr[q - 1];
if(A[q] == B[i])
q++;
if(q == m){
(*nr)++;
v[*nr] = i - m + 1;
if(*nr == 999)
return;
q = pr[q - 1];
}
}
}