Pagini recente » Cod sursa (job #1278328) | Cod sursa (job #1565653) | Cod sursa (job #1903239) | Cod sursa (job #19971) | Cod sursa (job #2298406)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string x, pat;
vector<int> phi, sol;
int main()
{
f >> pat >> x;
x = pat + "#" + x;
phi.resize(x.size(), 0);
for(int i = 1; i < x.size(); i++) {
int rez = phi[i-1];
while(rez && x[i] != x[rez])
rez = phi[rez - 1];
if(x[i] == x[rez]) rez++;
phi[i] = rez;
}
for(int i = 0; i < x.size(); i++) {
if(phi[i] == pat.size()) sol.push_back(i);
}
g << sol.size() << "\n";
for (auto i : sol)
g << i - pat.size() - (pat.size() - 1) - 1<< " ";
g << "\n";
return 0;
}