Pagini recente » Cod sursa (job #2570698) | Istoria paginii runda/oni_11_12_1 | Istoria paginii runda/oji2021/clasament | Cod sursa (job #2025583) | Cod sursa (job #2433138)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ofstream fout("abc2.out");
class InParser {
public:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
};
InParser fin("abc2.in");
struct item
{
string word;
int hashed;
};
item dictionary[50010];
int dicSize = 0;
string sir;
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;
}
inline void calcH(int m)
{
for(int i = 0; i<m-1; i++)
h=(h*dictionarySize)%prime;
}
inline bool compare(const item& f,const item& s)
{
return f.hashed<s.hashed;
}
inline bool compare2(const item& f,const int& s)
{
return f.hashed<s;
}
void read()
{
string temp="";
char c;
c = fin.read_ch();
while(c!='\n')
sir+=c-'a'+1,c = fin.read_ch();
while(c=fin.read_ch())
{
if(c=='\n')
{
dictionary[dicSize++]={temp,hashf(temp)};
temp="";
}
else
{
temp+=(c-'a'+1);
}
}
dicSize--;
calcH(dictionary[0].word.size());
sort(dictionary,dictionary+dicSize,compare);
}
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++)
{
item* j = lower_bound(dictionary,dictionary+dicSize,f,compare2);
while(j->hashed==f)
{
bool isEqual=true;
for(int d = 0;d<wordSize;d++)
{
if(j->word[d]!=sir[i+d])
isEqual=false;
}
if(isEqual){
times++;
break;
}
j++;
}
if(i<sir.size()-wordSize)
{
f = (dictionarySize*(f-sir[i]*h)+sir[i+wordSize])%prime;
while(f<0)
f+=prime;
}
}
fout<<times<<'\n';
}
int main()
{
read();
solve();
return 0;
}