Pagini recente » Cod sursa (job #487786) | Cod sursa (job #712638) | Cod sursa (job #2185401) | Cod sursa (job #2604169) | Cod sursa (job #789458)
Cod sursa(job #789458)
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2000005;
int sol[N], d[N], dPrim[N];
char text[N], pattern[N];
void read() {
assert(freopen("strmatch.in", "r", stdin) != NULL);
assert(freopen("strmatch.out", "w", stdout) != NULL);
assert(scanf("%s %s", pattern + 1, text + 1) == 2);
}
void zalgorithm() {
int n = strlen(pattern + 1);
int best;
d[1] = 0;
best = 0;
for (int i = 2; i <= n; ++i) {
if (best + d[best] >= i)
d[i] = min(d[i - best + 1], best + d[best] - i);
while (i + d[i] <= n && pattern[d[i] + 1] == pattern[i + d[i]])
++d[i];
if (i + d[i] > best + d[best])
best = i;
}
}
void match() {
int n = strlen(text + 1);
int m = strlen(pattern + 1);
int best;
best = 0;
for (int i = 1; i <= n; ++i) {
if (best + dPrim[best] >= i)
dPrim[i] = min(d[i - best + 1], best + dPrim[best] - i);
while (i + dPrim[i] <= n && dPrim[i] + 1 <= m && pattern[dPrim[i] + 1] == text[i + dPrim[i]])
++dPrim[i];
if (i + dPrim[i] > best + dPrim[best])
best = i;
if (dPrim[i] == m)
sol[++sol[0]] = i;
}
}
void write() {
printf("%d\n", sol[0]);
for (int i = 1; i <= min(sol[0], 1000); ++i)
printf("%d ", sol[i] - 1);
}
int main() {
read();
zalgorithm();
match();
write();
}