Pagini recente » Cod sursa (job #1965656) | Cod sursa (job #1015308) | Cod sursa (job #2610999) | Cod sursa (job #3229149) | Cod sursa (job #2526100)
#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<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++;
fout<<nr;
}
int main()
{
fin>>a>>b;
hasha();
hashb();
powerA(b.size());
sol();
return 0;
}