Pagini recente » Cod sursa (job #304235) | Cod sursa (job #2203847) | Cod sursa (job #3201208) | Cod sursa (job #1495460) | Cod sursa (job #2417680)
#include <bits/stdc++.h>
#define lld long long
#define mod 10007
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector<unsigned int>dt[mod+1];
char s[10000005], p[25];
int ln,lp, ans;
unsigned int wh;
unsigned int hsh, pw[25];
const unsigned int pww = 3;
bool ok;
int main()
{
fin>>s;
pw[0] = 1;
for (int i=1; i<20; ++i)
pw[i] = pw[i-1] * pww;
fin>>p;
lp = strlen(p);
do
{
hsh = 0;
for (int i=lp-1; i>=0; --i)
hsh = hsh + (p[i]-'a')*pw[lp-i-1];
wh = hsh % mod;
ok = false;
for (int j=0; j<dt[wh].size(); ++j)
if (dt[wh][j] == hsh)
{
ok = true;
break;
}
if (!ok)
dt[wh].push_back(hsh);
}
while (fin>>p);
hsh = 0;
for (int i=lp-1; i>=0; --i)
{
s[i]-='a';
hsh = hsh + s[i]*pw[lp-i-1];
}
wh = hsh % mod;
for (int j=0; j<dt[wh].size(); ++j)
if (dt[wh][j] == hsh)
{
++ans;
break;
}
for (int i=lp; s[i]; ++i)
{
s[i]-='a';
hsh = (hsh - s[i-lp]*pw[lp-1]) *pww + s[i];
wh = hsh%mod;
for (int j=0; j<dt[wh].size(); ++j)
if (dt[wh][j] == hsh)
{
++ans;
break;
}
}
fout<<ans<<'\n';
return 0;
}