Pagini recente » Autentificare | Cod sursa (job #2013821) | Cod sursa (job #2055056) | Cod sursa (job #2013747) | Cod sursa (job #1687112)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e6 + 10;
int asize , bsize , nr;
vector < int > v;
char a[nmax] , b[nmax];
int phi[nmax];
void bagaphi()
{
int k = 0;
phi[1] = k;
for (int i = 2; i <= asize; ++i)
{
while (k && a[k+1] != a[i]) k = phi[k];
if (a[k+1] == a[i]) k++;
phi[i] = k;
}
}
void bagakmp()
{
int k = 0;
for (int i = 1; i <= bsize; ++i)
{
while (k && a[k+1] != b[i]) k = phi[k];
if (a[k+1] == b[i]) k++;
if (k == asize)
{
nr++;
if (nr <= 1000) v.push_back(i-asize);
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> (a + 1) >> (b + 1);
asize = strlen(a+1);
bsize = strlen(b+1);
bagaphi();
bagakmp();
fout << nr << '\n';
for (auto &it : v) fout << it << ' ';
return 0;
}