Pagini recente » Cod sursa (job #2848137) | Cod sursa (job #389832) | Cod sursa (job #552317) | Cod sursa (job #3291094) | Cod sursa (job #1726109)
#include <fstream>
#include <vector>
#define tip long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
tip k,n,ha,hb,cnt,p,i,j,ix,px,ap[1010],putere(tip,tip),x=101,H=1000000007;
int main()
{
f>>A>>B;
k=A.size();
n=B.size();
for(i=0,p=1;i<k;i++,p=(p*x)%H)
{
ha=(ha+A[i]*p)%H;
hb=(hb+B[i]*p)%H;
}
if(ha==hb)
{
cnt++;
ap[cnt]=0;
}
ix=putere(x,H-2);
px=putere(x,k-1);
for(i=0,j=k;j<n;i++,j++)
{
hb=((hb+H-B[i])*ix+B[j]*px)%H;
if(ha==hb)
{
cnt++;
if(cnt<=1000)
ap[cnt]=i+1;
}
}
g<<cnt<<'\n';
if(cnt>1000)
cnt=1000;
for(i=1;i<=cnt;i++)
g<<ap[i]<<' ';
return 0;
}
tip putere(tip baza,tip expo)
{
tip rez=1;
while(expo)
{
if(expo%2)
rez=(rez*baza)%H;
baza=(baza*baza)%H;
expo/=2;
}
return rez;
}