Pagini recente » Cod sursa (job #2812971) | Cod sursa (job #1952792) | Cod sursa (job #2188738) | Cod sursa (job #2404829) | Cod sursa (job #2238689)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
vector<int> ans;
void zArrcalc(string pat, int Z[]){
int n = pat.size();
int L, R, k;
L = R = 0;
for(int i = 1; i < n; ++i)
{
if (i > R)
{
L = R = i;
while(R<n && pat[R-L] == pat[R])
R++;
Z[i] = R-L;
R--;
}
else
{
k = i-L;
if (Z[k] < R-i+1)
Z[i] = Z[k];
else
{
L = i;
while(R<n && pat[R-L] == pat[R])
R++;
Z[i] = R-L;
R--;
}
}
}
}
void Zsearch(string pat, string txt){
string concat = pat + "$" + txt;
int l = concat.size();
int Z[l];
zArrcalc(concat, Z);
for(int i = 0; i < l; ++i)
{
if(Z[i] == int(pat.size()))
ans.push_back(i - pat.size() - 1);
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string word, phrase;
fin >> word >> phrase;
Zsearch(word, phrase);
fout << ans.size() << "\n";
for(int i = 0; i < int(ans.size()); ++i)
fout << ans[i] << " ";
return 0;
}