Pagini recente » Cod sursa (job #1929020) | Cod sursa (job #2793923) | Cod sursa (job #3125430) | Cod sursa (job #2329529) | Cod sursa (job #2429189)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 2000005
int next[MAX];
void initnext(char *p){
int i, j, M = strlen(p) -1;
next[0] = -1;
for(i = 0, j = -1; i < M; i++, j++, next[i] = j){
while((j>=0) && (p[i] != p[j])){
j = next[j];
}
}
}
int cautKMP(char *p, char *a){
int i, j;
int N = strlen(a) -1;
int M = strlen(p) -1;
initnext(p);
for(i = 0, j = 0; i < N && j < M; i++,j++){
while((j>=0) && a[i] != p[j]){
j = next[j];
}
}
if(j == M) {
return i-M;
}
else return i;
}
int main(){
char *P, *A, *a;
P = calloc(MAX, sizeof(char));
A = calloc(MAX, sizeof(char));
int nr = 0, i, k;
int *v = calloc(MAX, sizeof(int));
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(P, MAX, stdin);
fgets(A, MAX, stdin);
int M = strlen(A) -1;
// int N = strlen(P) -1;
a = A;
for(i = 0; i < M; i++){
k = cautKMP(P,a);
if(k != M) {
if(nr) v[nr] = v[nr-1] + k + 1;
else v[nr] = k;
nr++;
}
a = a+k+1;
M -= k + 1;
}
printf("%d\n", nr);
for(k = 0; k < nr; k++){
printf("%d ", v[k]);
}
free(P);
free(A);
free(v);
return 0;
}