Pagini recente » Cod sursa (job #1095946) | Cod sursa (job #3295074) | Cod sursa (job #1100832) | Cod sursa (job #410544) | Cod sursa (job #3251028)
#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 q=666013,p=100003,ha,hb,ip,pn;
int64_t Q=100003,P=666013,HA,HB,IP,PN;
int64_t putere(int64_t b,int64_t e,int q)
{
if(e==0)
return 1;
int64_t r=putere(b,e/2,q);
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;
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;
HB=(HB*P+B[i])%Q;
}
ip=putere(p,q-2,q); /// ip = inversul modular al lui p modulo q
pn=putere(p,n-1,q); /// pn = p^(n-1) modulo q
IP=putere(P,Q-2,Q); /// ip = inversul modular al lui p modulo q
PN=putere(P,n-1,Q); /// pn = p^(n-1) modulo q
if(ha==hb && 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;
HB=(HB-B[st]+Q)%Q;st++;
/// se imparte prin p
hb=hb*ip%q;
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;
HB=(HB+PN*B[dr])%Q;
if(hb==ha && HB==HA)
{
sol++;
if(sol<=1000)
poz.push_back(st);
}
}
g<<sol<<'\n';
for(auto it:poz)
g<<it<<' ';
g<<'\n';
return 0;
}