Pagini recente » Cod sursa (job #2219852) | Cod sursa (job #139250) | Cod sursa (job #1238128) | Cod sursa (job #2897076) | Cod sursa (job #2298631)
#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() + pat.size() + 3, 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 (int i = 0; i < sol.size() && i < 1000; i++)
g << sol[i] - pat.size() - (pat.size() - 1) - 1 << " ";
g << "\n";
return 0;
}