Pagini recente » Cod sursa (job #2633714) | Cod sursa (job #1082079) | Cod sursa (job #647427) | Cod sursa (job #1133446) | Cod sursa (job #2634450)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("abc2.in");
ofstream g ("abc2.out");
typedef pair < int, int > PII;
const int NMAX = 1e7 + 5, LMAX = 25, MMAX = 5e4 + 5;
const int Mod = 666013;
int N, M, L;
char S[NMAX], A[LMAX];
unsigned int Key = 0;
unsigned int Where[MMAX], Last[(Mod + 5)], pos[MMAX];
unsigned int Val[MMAX];
int ans = 0;
static inline unsigned int lgput (unsigned int n, unsigned int p)
{
unsigned int ans = 1, aux = n;
for(int i = 0; (1 << i) <= p; ++i)
{
if(p & (1 << i))
ans *= aux;
aux *= aux;
}
return ans;
}
static inline bool Ok (unsigned int k)
{
for(int i = Last[k % Mod]; i; i = pos[i])
if(Val[i] == k)
return 1;
return 0;
}
int main()
{
f.tie(nullptr);
f >> (S + 1);
N = (int)strlen(S + 1);
while(f >> (A + 1))
{
L = (int)strlen(A + 1), Key = 0;
for(int i = 1; i <= L; ++i)
Key = Key * 3 + (int)(A[i] - 'a');
if(Ok(Key))
continue;
Where[++M] = Key % Mod;
Val[M] = Key;
if(Last[Key % Mod])
pos[M] = Last[Key % Mod];
Last[Key % Mod] = M;
}
Key = 0;
for(int i = 1; i <= L; ++i)
Key = Key * 3 + (S[i] - 'a');
if(Ok(Key))
++ans;
unsigned int p = lgput(3, (L - 1));
for(int i = (L + 1); i <= N; ++i)
{
unsigned int Diff = p * (S[i - L] - 'a');
Key = (Key - Diff) * 3 + (S[i] - 'a');
if(Ok(Key))
++ans;
}
g << ans << '\n';
return 0;
}