Pagini recente » Cod sursa (job #817047) | Cod sursa (job #2694076) | Cod sursa (job #111828) | Cod sursa (job #1773745) | Cod sursa (job #2106872)
#include <bits/stdc++.h>
using namespace std;
const int LenMax = 10000005;
const int WordLenMax = 30;
char Text[LenMax], Word[WordLenMax];
int TextSize, WordSize;
const int Base = 3;
const int Modulo = 233197;
vector <unsigned int> Lists[Modulo];
void insertHash(unsigned int Value)
{
int key = Value % Modulo;
Lists[key].push_back(Value);
}
bool findHash(unsigned int Value)
{
int key = Value % Modulo;
for(auto it : Lists[key])
if(it == Value)
return 1;
return 0;
}
int main()
{
ifstream cin("abc2.in");
ofstream cout("abc2.out");
cin >> Text;
TextSize = strlen(Text);
while(cin >> Word)
{
WordSize = strlen(Word);
unsigned int hashCode = 0;
for(int i = 0; i < WordSize; i++)
hashCode = hashCode * Base + Word[i] - 'a';
insertHash(hashCode);
}
if(TextSize < WordSize)
{
cout << "0\n";
return 0;
}
unsigned int Power = 1;
for(int i = 1; i < WordSize; i++)
Power *= Base;
unsigned int hashCode = 0;
for(int i = 0; i < WordSize; i++)
hashCode = hashCode * Base + Text[i] - 'a';
int answer = 0;
if(findHash(hashCode))
answer++;
for(int i = WordSize; i < TextSize; i++)
{
hashCode -= (Text[i - WordSize] - 'a') * Power;
hashCode = hashCode * Base + Text[i] - 'a';
if(findHash(hashCode))
answer++;
}
cout << answer << "\n";
return 0;
}