Pagini recente » iconcurs19 | Cod sursa (job #1342848) | Cod sursa (job #3125533) | Cod sursa (job #185470) | Cod sursa (job #2482721)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXS = 2e6 + 10, MAXN = 1e4;
char sub[MAXS], str[MAXS];
int len[MAXS], pos[MAXN], n, m, k;
void read() {
fin.getline(sub + 1, MAXS);
fin.getline(str + 1, MAXS);
m = strlen(sub + 1);
n = strlen(str + 1);
}
void preprocess() {
for (int i = 2, j = 0; i <= m; ++i) {
while (j && sub[j + 1] != sub[i])
j = pos[j];
if (sub[j + 1] == sub[i])
len[i] = ++j;
}
}
void kmp() {
for (int i = 1, j = 0; i <= n; ++i) {
while (j && sub[j + 1] != str[i])
j = pos[j];
if (sub[j + 1] == str[i]) {
++j;
if (j == m) {
if (k < 1000)
pos[k] = i - j;
++k;
j = len[j];
}
}
}
}
void print() {
fout << k << '\n';
if (k > 1000)
k = 1000;
for (int i = 0; i < k; ++i)
fout << pos[i] << ' ';
}
int main() {
read();
preprocess();
kmp();
print();
return 0;
}