Pagini recente » Cod sursa (job #130340) | Cod sursa (job #2019515) | Cod sursa (job #1606539) | Cod sursa (job #1110757) | Cod sursa (job #2634426)
#include <iostream>
#include <unordered_map>
using namespace std;
const int NMAX = 1e7 + 5;
const int Base = 131, Mod = 1e9 + 7;
int N;
char S[NMAX];
int L = 0;
unordered_map < int, bool > mp;
int ans = 0;
namespace InParser
{
static const int BSIZE = (1 << 16);
static int pos = BSIZE - 1;
static char buff[BSIZE];
static inline char Char ()
{
++pos;
if(pos == BSIZE)
{
pos = 0;
int n = fread(buff, 1, BSIZE, stdin);
if(n != BSIZE)
for(int i = n; i < BSIZE; ++i)
buff[i] = 0;
}
return buff[pos];
}
};
static inline int lgput (int n, int p)
{
int ans = 1, aux = n;
for(int i = 0; (1 << i) <= p; ++i)
{
if(p & (1 << i))
ans = (1LL * ans * aux) % (1LL * Mod);
aux = (1LL * aux * aux) % (1LL * Mod);
}
return ans;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
for( ; ; )
{
char Ch = InParser :: Char();
if(Ch >= 'a' && Ch <= 'z')
S[++N] = Ch;
else
break;
}
int Key = 0;
for( ; ; )
{
char Ch = InParser :: Char();
if(Ch >= 'a' && Ch <= 'z')
{
++L;
Key = ((1LL * Key * Base) % (1LL * Mod) + (int)(Ch - 'a')) % (1LL * Mod);
}
else
break;
}
mp[Key] = 1;
bool Ok = 1;
for( ; Ok; )
{
Key = 0;
bool found = 0;
for(int i = 1; i <= L && Ok; ++i)
{
char Ch = InParser :: Char();
if(Ch >= 'a' && Ch <= 'z')
Key = ((1LL * Key * Base) % (1LL * Mod) + (int)(Ch - 'a')) % (1LL * Mod), found = 1;
else
{
Ok = 0;
break;
}
}
if(found)
mp[Key] = 1, InParser :: Char();
}
Key = 0;
for(int i = 1; i <= L; ++i)
Key = ((1LL * Key * Base) % (1LL * Mod) + (int)(S[i] - 'a')) % (1LL * Mod);
if(mp[Key])
++ans;
int p = lgput(Base, (L - 1));
for(int i = (L + 1); i <= N; ++i)
{
int Diff = (1LL * p * (int)(S[i - L] - 'a')) % (1LL * Mod);
Key -= Diff;
if(Key < 0)
Key += Mod;
Key = (1LL * Key * Base) % (1LL * Mod);
Key = (Key + (int)(S[i] - 'a')) % Mod;
if(mp[Key])
++ans;
}
printf("%d\n", ans);
return 0;
}