Pagini recente » Cod sursa (job #2368548) | Cod sursa (job #1714782) | Cod sursa (job #2282646) | Cod sursa (job #72255) | Cod sursa (job #2969240)
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001],b[2000001],la,lb;
ull n,sol[2000001];
#define M 100007
#define M1 100021
void citire()
{
fin>>a;
fin.get();
fin>>b;
la=strlen(a);
lb=strlen(b);
}
void rabinkarp()
{
ull ha=0,hb=0,ha1=0,hb1=0;
ull p=73;
ull p1=1,p2=1;
for(ull i=0;i<la;i++){
ha=(ha*p+a[i])%M;
ha1=(ha1*p+a[i])%M1;
if(i!=0){
p1=(p1*p)%M;
p2=(p2*p)%M1;
}
}
for(ull i=0;i<la;i++){
hb=(hb*p+b[i])%M;
hb1=(hb1*p+b[i])%M1;
}
if(la>lb)
{
fout<<0;
return ;
}
//fout<<ha<<" "<<ha1<<" "<<hb<<" "<<hb1<<"\n";
if(ha==hb && ha1==hb1){
sol[0]=1;
n++;
}
// fout<<p<<" "<<p1<<" "<<p2<<"\n";
for(ull i=la;i<lb;i++)
{
hb=((hb-(b[i-la]*p1)%M+M)*p+b[i])%M;
hb1=((hb1-(b[i-la]*p2)%M1+M1)*p+b[i])%M1;
if(ha==hb && ha1==hb1)
sol[i-la+1]=1,n++;
}
fout<<n<<"\n";
n=0;
for(ull i=0;i<lb && n<1000;i++)
if(sol[i]){
fout<<i<<" ";
n++;
}
}
int main()
{
citire();
rabinkarp();
return 0;
}