Pagini recente » Cod sursa (job #3251952) | Cod sursa (job #2851019) | Visuian Mihai | Cod sursa (job #2701819) | Cod sursa (job #1974975)
//#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string t, p;
int n, m, tot;
vector<int> ans;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main()
{
cin >> p >> t;
n = t.size();
m = p.size();
t.insert(0, "#");
p.insert(0, "#");
vector<int> pref(m + 1);
pref[0] = pref[1] = 0;
for (int i = 2; i <= m; ++i) {
int pos = pref[i - 1];
while (p[pref[pos] + 1] != p[i] && pos > 0) {
pos = pref[pos];
}
pref[i] = pref[pos] + int(p[pos + 1] == p[i]);
}
// for (int i = 1; i <= m; ++i) {
// cout << pref[i] << ' ';
// }
// cout << '\n';
int i = 0, j = 0;
while (i < n) {
while (t[i + 1] != p[j + 1] && j > 0) {
j = pref[j];
}
j += int(p[j + 1] == t[i + 1]);
if (j == m) {
if (tot < 1000) {
ans.push_back(i);
}
tot++;
}
++i;
}
cout << tot << '\n';
for (auto x : ans) {
cout << x << ' ';
}
cout << '\n';
}