Pagini recente » Cod sursa (job #2407181) | Cod sursa (job #1134955) | Cod sursa (job #1691053) | Cod sursa (job #1252372) | Cod sursa (job #785285)
Cod sursa(job #785285)
#include <cassert>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2000005;
char text[N], pattern[N];
int prefix[N], sol[N];
void read() {
assert(freopen("strmatch.in", "r", stdin) != NULL);
assert(freopen("strmatch.out", "w", stdout) != NULL);
assert(scanf("%s", pattern + 1) == 1);
assert(scanf("%s", text + 1) == 1);
}
void Prefix() {
int p = 0;
int n = strlen(pattern + 1);
prefix[1] = 0;
for (int i = 2; i <= n; ++i) {
while (p > 0 && pattern[p + 1] != pattern[i])
p = prefix[p];
if (pattern[p + 1] == pattern[i])
++p;
prefix[i] = p;
}
}
void match() {
int p = 0;
int n = strlen(text + 1);
int m = strlen(pattern + 1);
for (int i = 1; i <= n; ++i) {
while (p > 0 && pattern[p + 1] != text[i])
p = prefix[p];
if (pattern[p + 1] == text[i])
++p;
if (p == m) {
sol[++sol[0]] = i - m;
p = prefix[p];
}
}
}
void write() {
int n = 1000 < sol[0] ? 1000:sol[0];
printf("%d\n", sol[0]);
for (int i = 1; i <= n; ++i)
printf("%d ", sol[i]);
}
int main() {
read();
Prefix();
match();
write();
}