Pagini recente » Cod sursa (job #2865201) | Cod sursa (job #311498) | Cod sursa (job #3126782) | Cod sursa (job #2368830) | Cod sursa (job #2526104)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
const long long N=999989977,A=699299929;
long long ha;
vector<int>v;
vector<long long>hb;
vector<long long>pA;
void hasha()
{
for(auto c : a)
ha=(ha*A+c)%N;
}
void hashb()
{
hb.push_back(b[0]);
for(int i=1;i<b.size();i++)
{
hb.push_back((hb[i-1]*A+b[i])%N);
}
}
void powerA(int L)
{
pA.push_back(1);
for(int x=1;x<=L;x++)
{
pA.push_back((pA[x-1]*A)%N);
}
}
long long getHash(int i,int j)
{
if(i==0)
return hb[j];
i--;
long long rez;
rez=(hb[j]-(hb[i]*pA[j-i])%N+N)%N;
return rez;
}
void sol()
{
int nr=0;
for(int i=0;i<b.size()-a.size();i++)
if(getHash(i,i+a.size()-1)==ha)
{
nr++;
v.push_back(i);
}
fout<<nr<<'\n';
for(auto x : v)
{
fout<<x<<' ';
}
}
int main()
{
fin>>a>>b;
hasha();
hashb();
powerA(b.size());
sol();
return 0;
}