Pagini recente » Cod sursa (job #2753885) | Cod sursa (job #1782349) | Cod sursa (job #885134) | Cod sursa (job #961560) | Cod sursa (job #1812396)
#include <fstream>
#include <iostream>
#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 1
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];
int atoii(char c)
{
if(c>='0' && c<='9') //cifra
return c-'0';
else if(c>='A' && c<='Z') //litera mare
return c - 'A' +10 ; //A =10, B=11, ...Z=35
else //litera mica
return c-'a' +36;
}
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=atoii(t[0]);
for(int i=1; i<m; ++i)
H=(H*base +atoii(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*atoii(w[0]) ) * base % mod;
hb=(hb+atoii(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;
}