Pagini recente » Cod sursa (job #76664) | Cod sursa (job #2698064) | Cod sursa (job #1727466) | Cod sursa (job #1298322) | Cod sursa (job #1812340)
#include <fstream>
#include <cstring>
#define lgmax 2000003
#define in "strmatch.in"
#define out "strmatch.out"
#define base 62 //26 (a-z) 26 (A-Z) 10 (0-9)
#define mod 20047297
typedef unsigned long long ull;
using namespace std;
ifstream fin(in);
ofstream fout(out);
ull Mx;
char A[lgmax],B[lgmax];
int ct=0,rez[1003];
ull HashPw(int bz,ull m)
{
ull P=1;
while(--m) // for(int i=1; i<=m-1; ++i)
P=(P*bz) %mod;
return P;
}
ull Hash(char *t,int m)
{
ull H=t[0];
for(int i=1; i<m; ++i)
H=(H*base +t[i]) %mod;
return H;
}
inline bool strcmpf(char *v,char *w,int m)
{
for(int i=0; v[i]; ++i)
if(v[i]!=w[i]) return false;
return true;
}
inline void HashSrch(char *v,const ull ha ,char *w,ull &hb,int poz,int m)
{
/*for(int i=0; w[i]; ++i) fout<<w[i];
fout<<"\n";*/
if(ha==hb && strcmpf(v,w,m))
{
++ct;
if(ct<=1000) rez[ct]=poz;
}
//se elimina valoarea caracterului cel mai semnificativ
hb=((hb - Mx*w[0] ) %mod ) * base % mod;
hb=(hb+w[m]) %mod;
if(hb<0) hb+=mod;
}
int main()
{
fin>>A>>B;
int m=strlen(A);
int n=strlen(B);
// prima data se stabileste constanta base ^ (m-1) % mod care va elimina caracterul
// cel mai semnificativ in timp constant
Mx=HashPw(base,m);
// determinam valoarea in baza 10 % mod a primelor m caractere din sirurile A si B
const ull ha=Hash(A,m);
ull hb=Hash(B,m);
//fout<<"ha= "<<ha<<"\n";
// pentru sirul B trebuie sa continuam subsecventa in functie de valoarea ei in
// baza 10 %mod , si pentru a nu calcula din nou tot, se elimina caracterul cel mai
// semnificativ si se adauga la capat cel mai nesemnificativ
for(int i=0; i<=n-m; ++i) // ultimul subsir va fi n-m+1, n-m+2,.... n-m+m ->din m caratctere.
{
//fout<<hb<<"\n";
HashSrch(A,ha,B+i,hb,i,m);
}
fout<<ct<<"\n";
for(int i=1; i<=ct; ++i)
fout<<rez[i]<<" ";
fin.close(); fout.close();
return 0;
}