Pagini recente » Cod sursa (job #1818305) | Cod sursa (job #57598) | Cod sursa (job #1234015) | Cod sursa (job #1653121) | Cod sursa (job #1834200)
//Algoritmul lui Rabin Karp
#include<fstream>
#include<vector>
#include<string>
#define P 73
#define MOD1 200003
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 ,trei[50];
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)
{
hash1 = 0;
for(i = 0; i < m ; i++)
{
hash1 = hash1 + trei[i] * (w[i] - 'a');
}
if(cauta(hash1) == 0)
adauga(hash1);
}
int main()
{
sol = 0;
fin >> a >> b;
n = a.length();
m = b.length();
p1 = p2 = 1;
trei[0] = 1;
for(i = 1; i <= m - 1; i++)
{
trei[i] = trei[i - 1] * 3;
}
cauta(b);
while(fin >> sir)
{
cauta(sir);
}
hash1 = 0;
for(i = 0; i < m ; i++)
{
hash1 = hash1 + (a[i] - 'a') * trei[i];
}
sol += cauta(hash1);
for(i = m ; i < n; i++)
{
hash1 = hash1 / 3;
hash1 = hash1 + ((a[i] - 'a') * trei[m - 1]);
sol += cauta(hash1);
}
fout << sol <<"\n";
}