Pagini recente » Cod sursa (job #132355) | Cod sursa (job #972753) | Cod sursa (job #1063946) | Cod sursa (job #3031760) | Cod sursa (job #2107976)
//#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 int> cuvinte[25000];
unsigned int puteri[25];
unsigned int rabin_karp(char* sir)
{
unsigned int rez=0;
for(int i=marime_karp-1; i>=0; i--)
{
rez+=(int)(sir[i]-'a')*puteri[marime_karp-i-1];
}
return rez;
}
int cautare(unsigned int key)
{
unsigned int aux=key;
key=key%25000;
vector <unsigned int>::iterator it;
for(it=cuvinte[key].begin(); it!=cuvinte[key].end(); it++)
{
if(*it==aux)return 1;
}
return 0;
}
void adaugare(unsigned int aux)
{
if(cautare(aux))return;
cuvinte[aux%25000].push_back(aux);
}
void generare_puteri()
{
puteri[0]=1;
for(int i=1; i<25; i++)puteri[i]=puteri[i-1]*3;
}
int main()
{
generare_puteri();
in>>sir;
char s[25];
unsigned int aux_key;
in>>s;
marime_karp=strlen(s);
aux_key=rabin_karp(s);
adaugare(aux_key);
while(1)
{
in>>s;
aux_key=rabin_karp(s);
adaugare(aux_key);
if(in.eof())break;
}
long nr=0;
int aux=strlen(sir);
unsigned int cheie=rabin_karp(sir);
for(int i=0; i<=aux-marime_karp; i++)
{
if(cautare(cheie))nr++;
cheie*=3;
cheie-=(unsigned int)(sir[i]-'a')*puteri[marime_karp];
cheie+=sir[i+marime_karp]-'a';
}
out<<nr;
return 0;
}