Pagini recente » Cod sursa (job #1488400) | Cod sursa (job #44837) | Cod sursa (job #611281) | Cod sursa (job #1847955) | Cod sursa (job #1834195)
//Algoritmul lui Rabin Karp
#include<fstream>
#include<vector>
#include<string>
#define P 73
#define MOD1 666013
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string a, sir, b;
unsigned i, n, m, k, j,aux,st,dr,x,y,t,poz,p1,p2,hash1,hash2contor,sol ;
vector <unsigned> myHash[MOD1];
void adauga(unsigned value1)
{
unsigned hashKey = value1 % MOD1, i;
myHash[hashKey].push_back(value1);
}
int cauta(unsigned value1)
{
unsigned gasit = 0, hashKey = value1 % MOD1;
int i;
for(i = 0; i < myHash[hashKey].size(); i++)
{
if(myHash[hashKey][i] == value1)
{
return 1;
}
}
return 0;
}
void cauta(string w)
{
//fout <<a<<"\n";
hash1 = 0;
unsigned trei = 1;
for(i = 0; i < m ; i++)
{
hash1 = hash1 + trei * (w[i] - 'a');
trei = trei * 3;
//hash2 = (hash2 * P + w[i]) % MOD2;
}
//fout<<hash1<<"\n";
adauga(hash1);
}
int main()
{
sol = 0;
fin >> a >> b;
n = a.length();
m = b.length();
p1 = p2 = 1;
for(i = 0; i < m - 1; i++)
{
p1 = (p1 * 3) % MOD1;
}
//fout<<p1<<"\n";
cauta(b);
while(fin >> sir)
{
//fout << sir<<"\n";
cauta(sir);
}
hash1 = 0;
unsigned trei = 1;
for(i = 0; i < m ; i++)
{
//fout<<i<<"\n";
hash1 = hash1 + (a[i] - 'a') * trei;
trei = trei * 3;
//hash2 = (hash2 * P + a[i]) % MOD2;
}
//fout<<hash1<<"\n";
sol += cauta(hash1);
for(i = m ; i < n; i++)
{
hash1 = hash1 / 3;
hash1 = hash1 + ((a[i] - 'a') * p1);
//fout<<hash1<<"\n";
//hash2 = ((hash2 - ((a[i - m] * p2) % MOD2) + MOD2 ) * P + a[i]) % MOD2;
sol += cauta(hash1);
//fout <<hash1<<" "<<hash2<<"\n";
}
fout << sol <<"\n";
//m = b.length();
//fout<<a<<" "<<b<<"\n";
/*p1 = p2 = 1;
initHash1 = initHash2 = 0;
//calculam functiile hash pentru sirul initial
for(i = 0; i < n; i++)
{
initHash1 = (initHash1 * P + a[i]) % MOD1;
initHash2 = (initHash2 * P + a[i]) % MOD2;
}
for(i = 0; i < n - 1; i++)
{
p1 = (p1 * P) % MOD1;
p2 = (p2 * P) % MOD2;
}
if(hash1 == initHash1 && hash2 == initHash2)
{
sol.push_back(0);
}
//eliminam elementul de pe pozitia i - n
for(i = n ; i < m; i++)
{
hash1 = ((hash1 - ((b[i - n] * p1) % MOD1) + MOD1 ) * P + b[i]) % MOD1;
hash2 = ((hash2 - ((b[i - n] * p2) % MOD2) + MOD2 ) * P + b[i]) % MOD2;
if(hash1 == initHash1 && hash2 == initHash2)
{
sol.push_back(i - n + 1);
}
}
if(sol.size() > 1000 ) contor = 1000;
else contor = sol.size();
fout << sol.size() << "\n";
for(i = 0; i < contor;i++)
{
fout << sol[i] <<" ";
}*/
}