Pagini recente » Cod sursa (job #1242927) | Cod sursa (job #2132384) | Cod sursa (job #309499) | Cod sursa (job #2140064) | Cod sursa (job #2483814)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> matching(string s, string p) {
s = p + "#" + s;
int need = (int) p.size(), n = (int) s.size(), j = 0;
vector<int> ps(n), ans;
ps[0] = 0;
for (int i = 1; i < n; i++) {
while (j && s[i] != s[j]) {
j = ps[j - 1];
}
if (s[i] == s[j]) {
j++;
ps[i] = j;
} else {
ps[i] = 0;
}
}
for (int i = need + 1; i < n; i++) {
if (ps[i] == need) {
ans.push_back(i - need - 1);
}
}
return ans;
}
int dt[100007];
int main() {
#ifdef INFOARENA
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
#endif // INFOARENA
/// freopen ("input", "r", stdin);
string p, s;
cin >> p >> s;
vector<int> ans = matching(s, p);
cout << (int) ans.size() << "\n";
if ((int) ans.size() > 1000) {
ans.resize(1000);
}
for (auto &i : ans) {
cout << i - (int) p.size() + 1 << " ";
}
cout << "\n";
return 0;
}