Pagini recente » Cod sursa (job #2860191) | Cod sursa (job #123651) | Cod sursa (job #1665761) | Cod sursa (job #1514703) | Cod sursa (job #2107621)
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
#define nr_karp 4
ifstream in("abc2.in");
ofstream out("abc2.out");
int marime_karp;
char sir[20001000];
vector<long long> cuvinte[86889];
long long rabin_karp(char* sir)
{
long long rez=0;
for(int i=marime_karp-1; i>=0; i--)
{
rez+=(int)(sir[i]-'a')*pow(nr_karp,marime_karp-i-1);
}
//cout<<sir<<' '<<rez<<'\n';
return rez;
}
int hash1(char* sir)
{
return rabin_karp(sir)%85889;
}
void adaugare(char* s)
{long long aux=rabin_karp(s);
int aux_con=hash1(s);
vector <long long>::iterator it;
for(it=cuvinte[aux_con].begin(); it!=cuvinte[aux_con].end(); it++)
{
// if(strcmp(*it,s)==0)return;
if(*it==aux)return;
}
cuvinte[aux_con].push_back(rabin_karp(s));
}
bool cautare(char* s,int key)
{
long long aux=rabin_karp(s);
vector <long long>::iterator it;
for(it=cuvinte[key].begin(); it!=cuvinte[key].end(); it++)
{
//cout<<*it<<'\n';
//if(strncmp(*it,s,marime_karp)==0)return 1;
if(*it==aux)return 1;
}
return 0;
}
int main()
{
in>>sir;
while(1)
{
char s[25];
in>>s;
marime_karp=strlen(s);
adaugare(s);
if(in.eof())break;
}
int nr=0;
int aux=strlen(sir);
int cheie=hash1(sir);
for(int i=0; i<=aux-marime_karp; i++)
{
// cout<<sir+i<<" "<<cheie<<'\n';
if(cautare(sir+i,cheie))nr++;
cheie=cheie*nr_karp;
cheie-=(sir[i]-'a')*pow(nr_karp,marime_karp);
cheie+=sir[i+marime_karp]-'a';
}
out<<nr;
return 0;
}