Pagini recente » Cod sursa (job #3241887) | Cod sursa (job #2274082) | Cod sursa (job #2241535) | Clasament time_ | Cod sursa (job #985254)
Cod sursa(job #985254)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char text[2000000], pat[2000000];
int results[1002];
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 length(char *t) {
int i;
for (i = 1; (t[i] >= 'A' && t[i] <='Z') || (t[i] >= 'a' && t[i] <= 'z') || (t[i] >= '0' && t[i] <= '9'); i++);
return i - 1;
}
int match() {
int m, n, i;
int r = 0;
prefix(pat);
n = length(text) + 1;
m = length(pat);
int k = 0;
for (i = 1; i <= n; i++) {
while (k && pat[k + 1] != text[i])
k = t[k];
if (pat[k + 1] == text[i])
k++;
if (k == m) {
k = t[m];
if (r < 1000)
results[r++] = i - m;
else
return r;
}
}
return r;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, r;
scanf("%s", pat+1);
pat[0] = ' ';
scanf("%s", text+1);
text[0] = ' ';
r = match();
printf("%d\n", r);
for (i = 0; i < r; i++)
printf("%d ", results[i]);
printf("\n");
return 0;
}