Pagini recente » Cod sursa (job #2513963) | Cod sursa (job #2141396) | Cod sursa (job #2376468) | Cod sursa (job #485726) | Cod sursa (job #2365397)
#include <cstdio>
#include <cstring>
#define LENGTH_MAX 2000010
char pattern[LENGTH_MAX], text[LENGTH_MAX];
int prefix[LENGTH_MAX], numberOfSolutions = 0, solutions[LENGTH_MAX];
void doPrefix(char* pattern, int length, int* prefix) {
int it = 1, k = 0;
prefix[0] = 0;
while (it < length) {
if (pattern[it] == pattern[k]) {
prefix[it] = ++k;
++it;
} else {
if (0 < k) {
k = prefix[k - 1];
} else {
k = prefix[it] = 0;
++it;
}
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", pattern, text);
int patternLength = strlen(pattern);
int textLength = strlen(text);
doPrefix(pattern, patternLength, prefix);
int it = 0, jt = 0;
while (jt < textLength) {
if (pattern[it] == text[jt]) {
++it;
++jt;
}
if (it == patternLength) {
solutions[numberOfSolutions++] = jt - it;
it = prefix[patternLength - 1];
} else if (pattern[it] != text[jt]) {
if (0 == it) {
++jt;
} else {
it = prefix[it - 1];
}
}
}
printf("%d\n", numberOfSolutions);
for (int it = 0; it < numberOfSolutions; ++it) {
printf("%d ", solutions[it]);
}
return 0;
}