Pagini recente » Cod sursa (job #193477) | Cod sursa (job #1031433) | Cod sursa (job #791940) | Cod sursa (job #1528220) | Cod sursa (job #1298015)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int pos[1000];
int pre[2000000];
int basicSearch(char *pattern, char *str)
{
char *p;
int len = strlen(pattern);
int lenStr = strlen(str);
int num = 0;
for (p = str; p - str <= lenStr - len + 1; p++) {
if (!strncmp(p, pattern, len) && num < 1000) {
pos[num++] = p - str;
}
}
return num;
}
void prefix(char *p)
{
int len = strlen(p);
int x;
int k = 0;
pre[0] = 0;
for (x = 1; x < len; x++) {
while (k > 0 && p[k] != p[x])
k = pre[k - 1];
if (p[k] == p[x])
k++;
pre[x] = k;
}
}
/**
* TODO
*/
int kmp(char *pattern, char *str)
{
int num = 0;
int m = strlen(pattern);
int n = strlen(str);
int d;
int k = 0;
prefix(pattern);
for (d = 0; d < n; d++) {
while (k > 0 && pattern[k] != str[d])
k = pre[k - 1];
if (pattern[k] == str[d])
k++;
if (k == m) {
if (num < 1000) {
pos[num] = d - k + 1;
}
num++;
k = pre[k - 1];
}
}
return num;
}
int main()
{
char *pattern;
char *str;
int n, i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
pattern = malloc(2000000);
str = malloc(2000000);
scanf("%s", pattern);
scanf("%s", str);
kmp(pattern, str);
// n = basicSearch(pattern, str);
n = kmp(pattern, str);
printf("%d\n", n);
for (i = 0; i < n; i++)
printf("%d ", pos[i]);
return 0;
}