Pagini recente » Cod sursa (job #1945628) | Cod sursa (job #1239307) | Cod sursa (job #2739947) | Cod sursa (job #1748345) | Cod sursa (job #985248)
Cod sursa(job #985248)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[2000000], p[2000000];
int results[5000];
int t[2000001];
void prefix(char *str) {
int n = strlen(str);
int i, k;
t[1] = 0;
k = 0;
for (i = 2; i <= n; i++) {
while(k && str[k + 1] != str[i])
k = t[k];
if (str[k + 1] == str[i])
k++;
t[i] = k;
}
}
int match(char *text, char *pat) {
int m, n, i;
int r = 0;
prefix(pat);
n = strlen(text);
m = strlen(pat) - 1;
int k = 0;
for (i = 1; i <= n; i++) {
while (k > 0 && pat[k + 1] != text[i])
k = t[k];
if (pat[k + 1] == text[i])
k++;
if (k == m) {
k = t[m];
results[r++] = i - m;
}
}
return r;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, r;
scanf("%s", p+1);
p[0] = ' ';
scanf("%s", s+1);
s[0] = ' ';
r = match(s, p);
printf("%d\n", r);
for (i = 0; i < r; i++)
printf("%d ", results[i]);
return 0;
}