Pagini recente » Cod sursa (job #796813) | Cod sursa (job #1419867) | Cod sursa (job #1537522) | Cod sursa (job #134139) | Cod sursa (job #2878591)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int base1=97,base2=107;
const int mod1=66667,mod2=666013;
int hashA,hashB;
int hashC,hashD;
int power1=1,power2=1;
const int NMAX=2000005;
char a[NMAX],b[NMAX];
int lenghtA,lenghtB;
int cnt;
int solutions[1002];
int precalculate1()
{
for(int i=1;i<=lenghtA-1;i++)
{
power1=(1LL*power1*base1)%mod1;
}
return power1;
}
int precalculate2()
{
for(int i=1;i<=lenghtA-1;i++)
{
power2=(1LL*power2*base2)%mod2;
}
}
void Create_HashA()
{
for(int i=0;i<lenghtA;i++)
{
hashA=((1LL*hashA*base1)%mod1+a[i])%mod1;
}
}
void Create_HashC()
{
for(int i=0;i<lenghtA;i++)
{
hashC=((1LL*hashC*base2)%mod2+a[i])%mod2;
}
}
void FindMatches()
{
for(int i=0;i<lenghtA;i++)
{
hashB=((1LL*hashB*base1)%mod1+b[i])%mod1;
}
for(int i=0;i<lenghtA;i++)
{
hashD=((1LL*hashD*base2)%mod2+b[i])%mod2;
}
//cout<<hashB<<" "<<hashC<<endl;
if(hashB==hashA and hashC==hashD)
{
cnt++;
if(cnt<=1000)
solutions[cnt]=0;
}
for(int i=lenghtA;i<lenghtB;i++)
{
hashB=(hashB-((1LL*(b[i-lenghtA])*power1)%mod1)+mod1)%mod1;
hashB=((1LL*hashB*base1)%mod1+b[i])%mod1;
hashD=(hashD-((1LL*(b[i-lenghtA])*power2)%mod2)+mod2)%mod2;
hashD=((1LL*hashD*base2)%mod2+b[i])%mod2;
if(hashA==hashB and hashC==hashD)
{
cnt++;
if(cnt<=1000)
solutions[cnt]=i-lenghtA+1;
}
}
}
int main()
{
cin>>a>>b;
lenghtA=strlen(a);
lenghtB=strlen(b);
if(lenghtA>lenghtB)
{
cout<<0;
return 0;
}
precalculate1();
precalculate2();
Create_HashA();
Create_HashC();
//FindMatches();
cout<<cnt<<'\n';
for(int i=1;i<=min(cnt,1000);i++)
cout<<solutions[i]<<" ";
return 0;
}