Pagini recente » Cod sursa (job #977355) | Cod sursa (job #830718) | Borderou de evaluare (job #1698045) | Cod sursa (job #2327314) | Cod sursa (job #1415548)
#include <cstdio>
#include <cstring>
char pattern[2000100], text[2000100];
int table[2000100], positions[1010];
int pattern_length, text_length, number_of_matches;
void prefix() {
table[0] = 0;
int match=0;
for (int i=1; i<pattern_length; ++i) {
while (match>0 && pattern[match] != pattern[i])
match = table[match-1];
if (pattern[match] == pattern[i])
++match;
table[i] = match;
}
}
void kmp() {
int match = 0;
for (int i=0; i<text_length; ++i) {
while (match>0 && pattern[match] != text[i])
match = table[match-1];
if (pattern[match] == text[i])
match++;
if (match == pattern_length && number_of_matches < 1000)
positions[number_of_matches++] = i - match + 1;
}
}
int main () {
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s", pattern);
scanf("%s", text);
pattern_length = strlen(pattern);
text_length = strlen(text);
prefix();
kmp();
printf("%d\n", number_of_matches);
for (int i=0; i<number_of_matches; ++i)
printf("%d ", positions[i]);
return 0;
}