Pagini recente » Cod sursa (job #607037) | Cod sursa (job #364587) | Cod sursa (job #312824) | Cod sursa (job #2235041) | Cod sursa (job #1996775)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, m, p[4000010], sol[2000005];
char a[4000010];
void kmp() {
int j = 0;
int i = 1;
while (i < m) {
if (a[i] == a[j]) {
p[i] = j + 1;
if (p[i] == n) {
sol[++sol[0]] = i;
}
i++;
j++;
} else {
if (j == 0) {
p[i] = 0;
i++;
} else {
j = p[j - 1];
}
}
}
}
int main()
{
in >> a;
n = strlen(a);
a[n] = '#';
in >> (a + n + 1);
m = strlen(a);
kmp();
out << sol[0] << "\n";
for (int i = 1; i <= min(sol[0], 1000); ++i) {
out << sol[i] - n - n << " ";
}
return 0;
}