Pagini recente » Cod sursa (job #441690) | Cod sursa (job #1377190) | Cod sursa (job #3252502) | Cod sursa (job #2498639) | Cod sursa (job #2107923)
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
int marime_karp;
char sir[10001000];
vector<unsigned long long> cuvinte[50000];
unsigned long long puteri[25];
unsigned long long rabin_karp(char* sir)
{
long long rez=0;
for(int i=marime_karp-1; i>=0; i--)
{
rez+=(int)(sir[i]-'a')*puteri[marime_karp-i-1];
}
//cout<<sir<<' '<<rez<<'\n';
return rez;
}
void adaugare(unsigned long long aux)
{
int aux_con=aux%50000;
vector <unsigned long long>::iterator it;
for(it=cuvinte[aux_con].begin(); it!=cuvinte[aux_con].end(); it++)
{
if(*it==aux)return;
}
cuvinte[aux_con].push_back(aux);
}
int cautare(unsigned long long key)
{
unsigned long long aux=key;
key=key%50000;
vector <unsigned long long>::iterator it;
for(it=cuvinte[key].begin(); it!=cuvinte[key].end(); it++)
{
if(*it==aux)return 1;
}
return 0;
}
void generare_puteri(){
puteri[0]=1;
for(int i=1;i<25;i++)puteri[i]=puteri[i-1]*4;
}
int main()
{
generare_puteri();
in>>sir;
char s[25];
unsigned long long aux_key;
while(1)
{
in>>s;
marime_karp=strlen(s);
aux_key=rabin_karp(s);
adaugare(aux_key);
if(in.eof())break;
}
long nr=0;
int aux=strlen(sir);
unsigned long long cheie=rabin_karp(sir);
for(int i=0; i<=aux-marime_karp; i++)
{
if(cautare(cheie))nr++;
cheie<<=2;
cheie^=(unsigned long long)(sir[i]-'a')*puteri[marime_karp];
cheie^=sir[i+marime_karp]-'a';
}
out<<nr;
return 0;
}