Pagini recente » Cod sursa (job #1514282) | Cod sursa (job #1997435) | Cod sursa (job #1738283) | Cod sursa (job #1682145) | Cod sursa (job #1944066)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("kmp.in");
ofstream g("kmp.out");
char a[2000002], b[2000002];
int i, q, lung[2000002], vs[1005], sol, n, m;
int main() {
f >> a+1 >> b+1;
n = strlen(a+1), m = strlen(b+1);
for (i = 2; i <= n; i++) {
while (a[q+1] != a[i] && q)
q = lung[q];
if (a[q+1] == a[i]) q++;
lung[i] = q;
}
for (i = 1, q = 0; i <= m; i++) {
while (a[q+1] != b[i] && q)
q = lung[q];
if (a[q+1] == b[i]) q++;
if (q == n) {
if (sol<=1000)
vs[++sol] = i-q;
}
}
g << sol << '\n';
for (i = 1; i <= sol; i++)
g << vs[i] << ' ';
return 0;
}