Pagini recente » Cod sursa (job #81066) | Cod sursa (job #2910917) | Cod sursa (job #1838821) | Cod sursa (job #42765) | Cod sursa (job #1996898)
#include <iostream>
#include <stdio.h>
#include <vector>
#define NMAX 2000010
using namespace std;
int pi[NMAX], N, M;
string s, t;
vector<int> ans;
void prefix() {
pi[1] = 0;
int k = 0;
for (int it = 2; it <= N; ++it) {
while (k > 0 && s[k + 1] != s[it]) {
k = pi[k];
}
if (s[k + 1] == s[it]) {
k += 1;
}
pi[it] = k;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> s >> t;
N = s.size();
M = t.size();
s = " " + s;
t = " " + t;
prefix();
int q = 0;
for (int it = 1; it <= M; ++it) {
while (q > 0 && s[q + 1] != t[it]) {
q = pi[q];
}
if (s[q + 1] == t[it]) {
q += 1;
}
if (N == q) {
if (ans.size() < 1000) ans.push_back(it);
q = pi[q];
}
}
cout << ans.size() << endl;
for (int it = 0; it < ans.size(); ++it) {
cout << ans[it] - N << " ";
}
return 0;
}