Pagini recente » Cod sursa (job #821892) | Cod sursa (job #2001263)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
vector<int> pi(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;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> pat >> tex;
vector<int> v = pi(pat);
vector<int> ans;
int p = 0;
int i_old = 0;
for (int i = 0; i < (int)tex.length(); i++) {
if (tex[i] == pat[p]) {
if (p == (int)pat.length()-1) {
ans.push_back(i_old);
p = v[p-1];
i = i_old + p;
i_old = i+1;
} else {
p++;
}
} else {
p = v[p-1];
i = i_old + p;
i_old = i+1;
}
}
fout << ans.size() << endl;
for (auto x: ans) {
fout << x << ' ';
}
fout << endl;
return 0;
}