Pagini recente » Cod sursa (job #2038538) | Cod sursa (job #1630853) | Cod sursa (job #1305775) | Cod sursa (job #1952291) | Cod sursa (job #2480861)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2000001, MAXS = 1000;
char sub[MAXN], str[MAXN];
int len[MAXN], sol[MAXN], n, m, k;
void read() {
fin.getline(sub + 1, MAXN);
fin.getline(str + 1, MAXN);
m = strlen(sub + 1);
n = strlen(str + 1);
}
void preprocess() {
len[1] = 1;
for (int i = 2, j = 1; i <= m;) {
if (sub[i] == sub[j])
len[i++] = ++j;
else if (j == 1)
len[i++] = 1;
else
j = len[i - 1];
}
}
void solve() {
for (int i = 1, j = 1; i <= n;) {
if (str[i] == sub[j]) {
if (j == m) {
if (k < MAXS)
sol[k] = i - j;
++k;
j = len[j];
}
else
++j;
++i;
}
else if (j == 1)
++i;
else
j = len[j - 1];
}
}
void print() {
fout << k << '\n';
k = min(k, MAXS);
for (int i = 0; i < k; ++i)
fout << sol[i] << ' ';
}
int main() {
read();
preprocess();
solve();
print();
return 0;
}