Pagini recente » Cod sursa (job #2577851) | Cod sursa (job #2961480) | Cod sursa (job #1843938) | Cod sursa (job #2193775) | Cod sursa (job #2001311)
#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;
}
template<typename T>
void printVec(const vector<T>& vec) {
for (auto x: vec) {
fout << x << ' ';
}
}
int main() {
string pat, tex;
// string tex = "ABAABACABADABACABACABADAA";
// string pat = "ABACABADABACABACABAD";
fin >> pat >> tex;
// ABA
// CABBCABABAB
vector<int> v = 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 = v[p - 1];
if (tex[i] == pat[p]) p += 1;
if (p == pat.length()) {
ans.push_back(i - pat.length() + 1);
p = v[p - 1];
}
}
fout << ans.size() << '\n';
printVec(ans);
return 0;
}