Pagini recente » Cod sursa (job #2626730) | Cod sursa (job #2903230) | Cod sursa (job #1319655) | Cod sursa (job #1225226) | Cod sursa (job #3251013)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
int n,m,sol;
vector<int> poz;
int64_t p=666013,q=100003,ha,hb,ip,pn;
int64_t putere(int64_t b,int64_t e)
{
if(e==0)
return 1;
int64_t r=putere(b,e/2);
r=r*r%q;
if(e%2==1)
r=r*b%q;
return r;
}
int main()
{
f>>A>>B;
n=A.size();
for(int i=n-1;i>=0;i--) /// calculam valoarea hash pentru pattern-ul A
ha=(ha*p+A[i])%q;
for(int i=n-1;i>=0;i--) /// calculam valoarea hash pentru pattern-ul A
hb=(hb*p+B[i])%q;
ip=putere(p,q-2); /// ip = inversul modular al lui p modulo q
pn=putere(p,n-1); /// pn = p^(n-1) modulo q
if(ha==hb)
{
sol++;
poz.push_back(0);
}
int st=0,dr=n-1;
m=B.size();
while(dr<m-1)
{
/// se scade din stanga
hb=(hb-B[st]+q)%q;st++;
/// se imparte prin p
hb=hb*ip%q;
/// se trece pe pozitia noua din dreapta la valoarea B[dr]
dr++;
/// se aduaga termenul B[dr] * p^n-1
hb=(hb+pn*B[dr])%q;
if(hb==ha)
{
sol++;
if(sol<=1000)
poz.push_back(st);
}
}
g<<sol<<'\n';
for(auto it:poz)
g<<it<<' ';
g<<'\n';
return 0;
}