Pagini recente » Cod sursa (job #174099) | Cod sursa (job #2493513) | oni_2012_11-12_ziua_1 | Cod sursa (job #2123308) | Cod sursa (job #2433163)
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ofstream fout("abc2.out");
const int prime = 1001;
const int dictionarySize = 3;
int wordSize;
string sir;
set<string> hmap[1001];
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;
}
void add(string a)
{
int Hash = hashf(a);
hmap[Hash].insert(a);
}
void calcH()
{
for(int i = 0;i<wordSize-1;i++)
h=(h*dictionarySize)%prime;
}
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;
}
};
void read()
{
InParser fin("abc2.in");
string temp;
char c;
c = fin.read_ch();
while(c!='\n')
sir+=c-'a'+1,c=fin.read_ch();
bool isDone = false;
while(c=fin.read_ch())
{
if(c=='\n')
{
if(!isDone){
wordSize = temp.size();
isDone=true;
}
add(temp);
temp="";
}
else
{
temp+=c-'a'+1;
}
}
calcH();
}
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 solve()
{
string temp = sir.substr(0,wordSize);
int f = hashf(temp);
int counter = 0;
for(int i = 0;i<=sir.size()-wordSize;i++)
{
temp = sir.substr(i,wordSize);
if(hmap[f].find(temp)!=hmap[f].end()){
counter++;
}
if(i<sir.size()-wordSize)
{
f=hashNext(temp,f,sir[i+wordSize]);
}
}
fout<<counter<<'\n';
}
int main()
{
read();
solve();
return 0;
}