Pagini recente » Cod sursa (job #2043925) | Cod sursa (job #3204471) | Cod sursa (job #1787344) | Cod sursa (job #1617581) | Cod sursa (job #1173492)
//RABIN KARP
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int NA,NB,pattern,text,pat,lg,sol[2000005];
const int baza=73;
const int prim=666013;
char A[2000005],B[2000005];
inline void Citire()
{
fin>>(A+1)>>(B+1);
}
inline bool Verifica(int poz)
{
int i,ca;
ca=NA;
for (i=poz;i>=poz-NA+1;i--)
{
if (B[i]!=A[ca])
return 0;
ca--;
}
return 1;
}
inline void Init()
{
int i,putere=1;
for (i=NA;i>=1;i--)
{
if (i==1)
pat=putere;
pattern+=((int)A[i]*putere)%prim;
putere*=baza;
putere%=prim;
}
putere=1;
for (i=NA;i>=1;i--)
{
text+=((int)B[i]*putere)%prim;
putere*=baza;
putere%=prim;
}
if (text==pattern)
if (Verifica(NA))
sol[++lg]=1;
}
inline void Rezolva()
{
int i;
NA=strlen(A+1);
NB=strlen(B+1);
Init();
for (i=NA+1;i<=NB;i++)
{
text=text-((int)B[i-NA]*pat)%prim;
if (text<0) text+=prim;
text=text*baza;
text+=(int)B[i];
text%=prim;
if (text==pattern)
if (Verifica(i))
sol[++lg]=i-NA;
}
}
int main()
{
Citire();
Rezolva();
fout<<lg<<"\n";
for (int i=1;i<=lg;i++)
fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}