Pagini recente » Cod sursa (job #1232420) | Istoria paginii runda/oni-2015-11-12 | arena | Istoria paginii runda/rhhrh3 | Cod sursa (job #2433088)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
struct item
{
string word;
int hashed;
};
vector<item> dictionary;
string sir;
short pows[21];
const int prime = 101;
const int dictionarySize = 3;
int h = 1;
int hashf(string a)
{
int r=0;
for(int i = 0;i<a.size();i++)
r = (dictionarySize*r+a[i])%prime;
return r;
}
int hashNext(string a,int hashA,char next)
{
int r = 1;
r = (dictionarySize*(hashA-a[0]*h)+next)%prime;
while(r<0)
r+=prime;
return r;
}
void calcH(int m)
{
for(int i = 0;i<m-1;i++)
h=(h*dictionarySize)%prime;
}
void read()
{
string temp;
fin>>sir;
for(int i = 0;i<sir.size();i++)
sir[i]=sir[i]-'a'+1;
while(fin>>temp)
{
for(int i = 0;i<temp.size();i++)
temp[i]=temp[i]-'a'+1;
dictionary.push_back({temp,hashf(temp)});
}
calcH(temp.size());
}
void solve()
{
int times = 0;
int wordSize = dictionary[0].word.size();
int f = hashf(sir.substr(0,wordSize));
for(int i = 0;i<=sir.size()-wordSize;i++)
{
//for(int j = i;j<wordSize+i;j++)
// cout<<(int)sir[j];
//cout<<" "<<f<<endl;
for(int j = 0;j<dictionary.size();j++)
{
if(f==dictionary[j].hashed)
{
if(dictionary[j].word.compare(sir.substr(i,wordSize))==0){
times++;
break;
}
}
}
if(i<sir.size()-wordSize)
{
f=hashNext(sir.substr(i,wordSize),f,sir[i+wordSize]);
}
}
fout<<times<<'\n';
}
int main()
{
read();
//for(int i = 0;i<dictionary.size();i++)
//{
// for(int j = 0;j<dictionary[i].word.size();j++)
// cout<<(int)dictionary[i].word[j];
// cout<<" "<<dictionary[i].hashed<<endl;
//}
solve();
return 0;
}