Pagini recente » Cod sursa (job #732328) | Borderou de evaluare (job #2237740) | Cod sursa (job #394986) | Borderou de evaluare (job #3173969) | Cod sursa (job #1771018)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> prefix_function (string Z) {
int n = (int) Z.length();
vector<int> F (n);
F[0]=0;
for (int i=1; i<n; ++i) {
int j = F[i-1];
while (j > 0 && Z[i] != Z[j])
j = F[j-1];
if (Z[i] == Z[j]) ++j;
F[i] = j;
}
return F;
}
vector <int> poz;
int main()
{
string p, t;
string a;
fin >> p >> t;
a=p+"#"+t;
vector<int> b(a.size());
b = prefix_function(a);
int ct = 0;
for(int i=0; i<b.size(); i++)
{
if(b[i]==p.size())
{
ct++;
poz.push_back(i-2*p.size());
}
}
fout << ct << '\n';
for(int i=0; i<ct; i++){
fout << poz[i] << ' ';
}
return 0;
}