Pagini recente » Cod sursa (job #2225541) | Cod sursa (job #1837946) | Cod sursa (job #2918296) | Cod sursa (job #2086541) | Cod sursa (job #873225)
Cod sursa(job #873225)
#include <cstdio>
#include <cassert>
#include <cstring>
#define MAX_N 2000001
#define MAX_Q 1001
int n1, n2;
int nr, ans[MAX_Q];
int pi[MAX_N];
char s1[MAX_N], s2[MAX_N];
inline void pull(char A[], int n) {
for (int i = n; i > 0; --i)
A[i] = A[i - 1];
A[0] = ' ';
}
inline int min(int x, int y) {
return (x < y) ? x : y;
}
void make_prefix() {
int q = 0;
for (int i = 2; i <= n1; ++i) {
while (q && s1[q + 1] != s1[i])
q = pi[q];
if (s1[q + 1] == s1[i])
++q;
pi[i] = q;
}
}
void write() {
printf("%d\n", nr);
for (int i = 1; i <= min(nr, 1000); ++i)
printf("%d ", ans[i]);
printf("\n");
}
int main() {
assert(freopen("strmatch.in", "r", stdin));
assert(freopen("strmatch.out", "w", stdout));
assert(gets(s1));
assert(gets(s2));
n1 = strlen(s1);
n2 = strlen(s2);
pull(s1, n1);
pull(s2, n2);
make_prefix();
int q = 0;
for (int i = 1; i <= n2; ++i) {
while (q && s1[q + 1] != s2[i])
q = pi[q];
if (s1[q + 1] == s2[i])
++q;
if (q == n1) {
q = pi[n1];
++nr;
if (nr <= 1000)
ans[nr] = i - n1;
}
}
write();
}