Pagini recente » Heist | Statisticile problemei Delfin | Profil tudorgalatan | Diferente pentru planificare/sedinta-20090316 intre reviziile 22 si 42 | Cod sursa (job #1974976)
//#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 = i - 1;
while (p[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';
}