Pagini recente » Cod sursa (job #2880261) | Cod sursa (job #1805678) | Cod sursa (job #2868084) | Cod sursa (job #1644915) | Cod sursa (job #2480852)
#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 = 2000010, MAXS = 1000;
char sub[MAXN], str[MAXN];
int len[MAXN], n, m, k;
vector<int> sol;
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];
}
}
void solve() {
for (int i = 1, j = 1; i <= n;) {
if (str[i] == sub[j]) {
if (j == m) {
if (k < MAXS)
sol.pb(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;
}