Pagini recente » Cod sursa (job #1441309) | Cod sursa (job #735910) | Cod sursa (job #3248338) | Cod sursa (job #1955311) | Cod sursa (job #1955171)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000005], b[2000005];
int n, m, i, q, lg[2000005], sol[1005], ns;
int main() {
f.getline(a+1, sizeof(a));
f.getline(b+1, sizeof(b));
n = strlen(a+1), m = strlen(b+1);
for (i = 2; i <= n; i++) {
while (a[q+1] != a[i] && q)
q = lg[q];
if (a[q+1] == a[i]) q++;
lg[i] = q;
} q = 0;
for (i = 1; i <= m; i++) {
while (a[q+1] != b[i] && q)
q = lg[q];
if (a[q+1] == b[i]) q++;
if (q == n) {
ns++;
if (ns<= 1000) sol[ns] = i-q;
q = lg[q];
}
}
g << ns << '\n';
ns= min(ns,1000);
for (i =1; i <= ns; i++) g << sol[i] << ' ';
return 0;
}