Pagini recente » Cod sursa (job #2174686) | Cod sursa (job #187724) | Cod sursa (job #963712) | Cod sursa (job #1820898) | Cod sursa (job #2291848)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#define MOD 20003
using namespace std;
vector <unsigned int> h[MOD];
inline int M(unsigned int x)
{
if(x < MOD)
return x;
return x%MOD;
}
inline unsigned int val(string S,int dim)
{
unsigned int x = 0, p3 = 1;
for (int i = dim - 1; i > -1; --i)
{
x += (S[i] - 'a') * p3;
p3 *= 3;
}
return x;
}
inline void Push(unsigned int x)
{
int p = M(x);
for (int i = 0; i < h[p].size(); ++i)
if(h[p][i] == x)
return;
h[p].push_back(x);
}
inline bool Search(unsigned int x)
{
int p = M(x);
for (int i = 0; i < h[p].size(); ++i)
if(h[p][i] == x)
return true;
return false;
}
int main()
{
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
string s,curr;
int i,n,k,cnt = 0;
unsigned x,P = 1;
fin >> s >> curr;
k = curr.size();
n = s.size();
for (i = 1; i < k; ++i)
P *=3;
x = val(curr,k);
Push(x);
while(fin >> curr)
{
x = val(curr,k);
Push(x);
}
x = val(s,k);
if(Search(x))
++cnt;
for(i = k; i < n; ++i)
{
x -= (s[i - k] - 'a') * P;
x = x * 3 + s[i] - 'a';
if(Search(x))
++cnt;
}
fout << cnt;
return 0;
}