Pagini recente » Cod sursa (job #3166856) | Cod sursa (job #2168258) | Cod sursa (job #2133600) | Cod sursa (job #696684) | Cod sursa (job #2417607)
#include <cstdio>
#include <unordered_map>
#include <fstream>
#include <iostream>
#include <string>
#define lld long long
#define mod 1000000007
using namespace std;
//FILE *fin=fopen("abc2.in","r");
ifstream fin("abc2.in");
FILE *fout=fopen("abc2.out","w");
unordered_map<string,int>ump;
string s, sact;
const lld pww = 31;
int ans, ln, n;
lld pw[20], expectedHash, currHash;
bool check(string sact)
{
n = sact.size();
if (n > ln) return 0;
expectedHash = currHash = 0LL;
for (int i=0; i<n; ++i)
{
expectedHash = (expectedHash + sact[i] * pw[n - i - 1]) % mod;
currHash = (currHash + s[i] * pw[n - i - 1]) % mod;
}
if (currHash == expectedHash) return true;
for (int i=n; i<ln; ++i)
{
currHash = (currHash - s[i - n] * pw[n-1]) % mod;
if (currHash < 0) currHash = mod + currHash;
currHash = (currHash * pww + s[i]) % mod;
if (currHash == expectedHash) return true;
}
return false;
}
int main()
{
fin>>s;
ln = s.size();
pw[0] = 1;
for (int i=1; i<20; ++i)
pw[i] = ( pw[i-1] * pww ) % mod;
while(fin>>sact)
++ump[sact];
for (auto x:ump)
if (check(x.first))
++ans;
fprintf(fout,"%d\n",ans);
return 0;
}