Pagini recente » Diferente pentru utilizator/tudormaxim intre reviziile 110 si 93 | Statistici Rusu Andrei (NeoAndrei) | Diferente pentru utilizator/iulianrotaru intre reviziile 13 si 14 | Statistici Marian Andreea (morandy13) | Cod sursa (job #1049969)
//Rabin-Karp
#include <stdio.h>
#include <cstring>
#include <vector>
using namespace std;
const int strLEN=2000002;
const int BASE=79;
const int MOD1=999983;
const int MOD2=999979;
char A[2000002],B[2000002];
vector <int> sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A,strLEN,stdin);
fgets(B,strLEN,stdin);
int nA=strlen(A)-1;
int nB=strlen(B)-1;
int hashA1,hashA2,hashB1,hashB2;
hashA1=hashA2=hashB1=hashB2=0;
int pow1,pow2;
pow1=pow2=1;
for(int i=0;i<nA;++i)
{
hashA1=(hashA1*BASE+A[i]-'0')%MOD1;
hashA2=(hashA2*BASE+A[i]-'0')%MOD2;
hashB1=(hashB1*BASE+B[i]-'0')%MOD1;
hashB2=(hashB2*BASE+B[i]-'0')%MOD2;
pow1=(pow1*BASE)%MOD1;
pow2=(pow2*BASE)%MOD2;
}
if(hashA1==hashB1&&hashA2==hashB2) sol.push_back(0);
for(int i=nA;i<nB;++i)
{
hashB1=((hashB1*BASE+B[i]-'0')%MOD1+MOD1-(pow1*(B[i-nA]-'0'))%MOD1)%MOD1;
hashB2=((hashB2*BASE+B[i]-'0')%MOD2+MOD2-(pow2*(B[i-nA]-'0'))%MOD2)%MOD2;
if(hashA1==hashB1&&hashA2==hashB2) sol.push_back(i-nA+1);
}
printf("%zu\n",sol.size());
for(vector <int>::iterator it=sol.begin();it!=sol.end()&&it-sol.begin()<1000;++it)
printf("%d ",*it);
printf("\n");
return 0;
}