Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Diferente pentru utilizator/bubu_the_kidd intre reviziile 3 si 2 | Monitorul de evaluare | Cod sursa (job #1959141)
#include <bits/stdc++.h>
#define baza 73
#define mod1 100007
#define mod2 100021
using namespace std;
string a,b;
int hasha1,hasha2,hashb1,hashb2,hb1=1,hb2=1,i,nr;
vector <int> v;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>a>>b;
int n=a.length(),m=b.length();
for (i=0; i<n; i++)
{
hasha1=(hasha1*baza+a[i]) % mod1;
hasha2=(hasha2*baza+a[i]) % mod2;
hashb1=(hashb1*baza+b[i]) % mod1;
hashb2=(hashb2*baza+b[i]) % mod2;
if (!i) continue;
hb1=(hb1*baza) % mod1;
hb2=(hb2*baza) % mod2;
}
for (i=0; i<=m-n; i++)
{
if (hasha1==hashb1 && hasha2==hashb2) nr++,v.push_back(i);
hashb1=((hashb1-(b[i]*hb1) % mod1 + mod1) * baza + b[i+n]) % mod1;
hashb2=((hashb2-(b[i]*hb2) % mod2 + mod2) * baza + b[i+n]) % mod2;
}
cout<<nr<<'\n';
for (i=0; i<min(1000,nr); i++)
cout<<v[i]<<" ";
}