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