Pagini recente » Cod sursa (job #130493) | Cod sursa (job #798479) | Cod sursa (job #2916190) | Cod sursa (job #1642962) | Cod sursa (job #1379065)
#include<fstream>
#include<vector>
#include<cstring>
#define LTMAX 10000001
using namespace std;
struct Hash
{
vector < vector<int> > ha;
int key;
Hash()
{
int i;
key=700001;
vector <int> v;
for(i=0; i<key; i++)
ha.push_back(v);
}
vector <int> :: iterator find(int value)
{
int list=value%key;
vector <int> :: iterator it;
for(it=ha[list].begin(); it!=ha[list].end(); it++)
if(*it==value)
return it;
return ha[list].end();
}
void insert(int value)
{
if(find(value)==ha[value%key].end())
ha[value%key].push_back(value);
}
bool exists(int value)
{
if(find(value)==ha[value%key].end())
return 0;
return 1;
}
};
char text[LTMAX];
char word[21];
int get_number(char str[])
{
int i;
int nr=0;
int l=strlen(str);
for(i=0; i<l; i++)
nr=nr*10+str[i]-'a';
return nr;
}
int main()
{
Hash h;
int lword;
int ltext;
int i;
int nr=0;
int total=0;
int p10=1;
ifstream f("abc2.in");
f>>text;
f>>word;
lword=strlen(word);
h.insert(get_number(word));
while(f>>word)
h.insert(get_number(word));
f.close();
ofstream g("abc2.out");
ltext=strlen(text);
if(lword>ltext)
{
g<<"0\n";
g.close();
return 0;
}
for(i=0; i<lword; i++)
{
p10*=10;
nr=nr*10+text[i]-'a';
}
p10/=10;
if(h.exists(nr))
total++;
for(i=lword; i<ltext;i++)
{
nr=(nr-p10*(text[i-lword]-'a'))*10+text[i]-'a';
if(h.exists(nr))
total++;
}
g<<total<<'\n';
g.close();
return 0;
}