Pagini recente » Cod sursa (job #816615) | Cod sursa (job #1001506) | Cod sursa (job #2816751) | Cod sursa (job #2429964) | Cod sursa (job #2634448)
#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 Base = 131, Mod = 666013;
int N, M;
char S[NMAX], A[LMAX];
int L;
unsigned int Key = 0;
int Where[MMAX], Val[MMAX], Last[(Mod + 5)], pos[MMAX];
int ans = 0;
static inline unsigned int lgput (int n, 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 (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 * Base + (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 * Base + (int)(S[i] - 'a');
if(Ok(Key))
++ans;
unsigned int p = lgput(Base, (L - 1));
for(int i = (L + 1); i <= N; ++i)
{
unsigned int Diff = p * (int)(S[i - L] - 'a');
Key = (Key - Diff) * Base + (int)(S[i] - 'a');
if(Ok(Key))
++ans;
}
g << ans << '\n';
return 0;
}