Pagini recente » Rating Dorian Pop (DorianPop) | Istoria paginii utilizator/cristy_sae | Monitorul de evaluare | Cod sursa (job #2169372) | Cod sursa (job #2001314)
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> pi(const string& p) {
int n = p.length();
vector<int> res(n);
res[0] = 0;
int l = 0;
for (int i = 1; i < n; i += 1) {
while (l > 0 && p[i] != p[l]) l = res[l - 1];
if (p[i] == p[l]) l += 1;
res[i] = l;
}
return res;
}
int main() {
string pat, tex;
fin >> pat >> tex;
vector<int> prefix = pi(pat);
vector<int> ans;
int p = 0;
int n = tex.length();
for (int i = 0; i < n; i += 1) {
while (p > 0 && tex[i] != pat[p]) p = prefix[p - 1];
if (tex[i] == pat[p]) p += 1;
if (p == pat.length()) {
ans.push_back(i - pat.length() + 1);
p = prefix[p - 1];
}
}
fout << ans.size() << '\n';
for (int i = 0, to = min(int(ans.size()), 1000); i < to; i += 1) {
fout << ans[i] << ' ';
}
return 0;
}