Pagini recente » Cod sursa (job #1640644) | Cod sursa (job #2147675) | Monitorul de evaluare | Cod sursa (job #1285759) | Cod sursa (job #1838128)
#include<iostream>
#include<fstream>
#include<string>
#define B1 130
#define B2 130
#define M1 1000000009
#define M2 1000000007
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
string a,b;
long long p1=1,p2=1,k1,k2,k3,k4;
int poz[1111];
int main()
{
int i,ante,j,n=0;
fin>>a>>b;
for(i=0;i<a.size();i++)
{
if(i>0) p1=(p1*B1)%M1;
if(i>0) p2=(p2*B2)%M2;
k1=(k1*B1+int(a[i]))%M1;
k2=(k2*B2+int(a[i]))%M2;
}
for(i=0;i<a.size();i++)
{
k3=(k3*B1+int(b[i]))%M1;
k4=(k4*B2+int(b[i]))%M2;
}
//cout<<k1<<" "<<k2<<"\n";
if(k1==k3 && k2==k4)
{
n++;
poz[n]=0;
}
for(i=a.size();i<b.size();i++)
{
ante=i-a.size();
k3=k3-p1*int(b[ante]);
k4=k4-p2*int(b[ante]);
k3=(((k3%M1+M1)%M1)*B1+int(b[i]))%M1;
k4=(((k4%M2+M2)%M2)*B2+int(b[i]))%M2;
if(k1==k3 && k2==k4)
{
n++;
if(n<1000) poz[n]=ante+1;
}
}
fout<<n<<"\n";
for(i=1;i<=min(1000,n);i++) fout<<poz[i]<<" ";
}