Pagini recente » Cod sursa (job #2750570) | Cod sursa (job #2954809) | Cod sursa (job #1955437) | Cod sursa (job #2248559) | Cod sursa (job #2167911)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 2000005
int min(int x, int y) {
return x < y ? x : y;
}
int* KMP(char* String, char* Pattern, int* size) {
int m = strlen(Pattern);
int n = strlen(String);
int *Pi = (int*)malloc(sizeof(int) * MAXN);
int* ans = (int*) malloc(sizeof(int) * MAXN);
memset(ans, 0, sizeof(ans));
int x = 0, i;
for (i = 1; i < m; i++) {
while (x > 0 && Pattern[x] != Pattern[i])
x = Pi[x - 1];
if (Pattern[x] == Pattern[i])
x++;
Pi[i] = x;
}
x = 0;
for (i = 0; i < n; i++) {
while (x > 0 && Pattern[x] != String[i])
x = Pi[x - 1];
if (Pattern[x] == String[i])
x++;
if (x == m) {
ans[(*size)++] = i - x + 1;
}
}
return ans;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char* String = (char*)malloc(sizeof(char) * MAXN);
char* Pattern = (char*) malloc(sizeof(char) * MAXN);
int size = 0, i;
scanf("%s", Pattern);
scanf("%s", String);
int* ans = KMP(String, Pattern, &size);
printf("%d \n", size);
for (i = 0; i < min(size, 1000); i++) {
printf("%d ", ans[i]);
}
printf("\n");
free(String);
free(Pattern);
free(ans);
return 0;
}