Pagini recente » Cod sursa (job #2664166) | Cod sursa (job #2855490) | Cod sursa (job #1360982) | Cod sursa (job #1303920) | Cod sursa (job #2480878)
#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], sol[MAXN], n, m, k;
void read() {
fin.getline(sub, MAXN);
fin.getline(str, MAXN);
m = strlen(sub);
n = strlen(str);
}
void preprocess() {
for (int i = 1, j = 0; i < m;) {
if (sub[i] == sub[j])
len[i++] = ++j;
else if (!j)
++i;
else
j = len[j - 1];
}
}
void solve() {
for (int i = 0, j = 0; i < n;) {
if (str[i] == sub[j]) {
++i, ++j;
if (j == m) {
if (k < MAXS)
sol[k] = i - j;
++k;
j = len[j - 1];
}
}
else if (!j)
++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;
}