Pagini recente » Cod sursa (job #2817418) | Cod sursa (job #2848730) | Cod sursa (job #1115331) | Cod sursa (job #860615) | Cod sursa (job #2634445)
#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_1 = 131, Mod_1 = 666013;
const int Base_2 = 137, Mod_2 = 666019;
int N, M, L;
char S[NMAX], A[LMAX];
unsigned int Key_1, Key_2;
int Where[MMAX], Val[MMAX], Last[(Mod_1 + 5)], pos[MMAX];
int ans = 0;
static inline int lgput (int n, int p, int Mod)
{
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;
}
static inline bool Ok (int k_1, int k_2)
{
for(int i = Last[k_1]; i; i = pos[i])
if(Val[i] == k_2)
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_1 = 0, Key_2 = 0;
for(int i = 1; i <= L; ++i)
{
Key_1 = ((Key_1 * Base_1) % Mod_1 + (int)(A[i] - 'a')) % Mod_1;
Key_2 = ((Key_2 * Base_2) % Mod_2 + (int)(A[i] - 'a')) % Mod_2;
}
if(Ok(Key_1, Key_2))
continue;
Where[++M] = Key_1;
Val[M] = Key_2;
if(Last[Key_1])
pos[M] = Last[Key_1];
Last[Key_1] = M;
}
Key_1 = 0, Key_2 = 0;
for(int i = 1; i <= L; ++i)
{
Key_1 = ((Key_1 * Base_1) % Mod_1 + (int)(S[i] - 'a')) % Mod_1;
Key_2 = ((Key_2 * Base_2) % Mod_2 + (int)(S[i] - 'a')) % Mod_2;
}
if(Ok(Key_1, Key_2))
++ans;
int p_1 = lgput(Base_1, (L - 1), Mod_1), p_2 = lgput(Base_2, (L - 1), Mod_2);
for(int i = (L + 1); i <= N; ++i)
{
int Diff_1 = (p_1 * (int)(S[i - L] - 'a')) % Mod_1;
int Diff_2 = (p_2 * (int)(S[i - L] - 'a')) % Mod_2;
Key_1 -= Diff_1, Key_2 -= Diff_2;
if(Key_1 < 0)
Key_1 += Mod_1;
if(Key_2 < 0)
Key_2 += Mod_2;
Key_1 = (Key_1 * Base_1) % Mod_1, Key_2 = (Key_2 * Base_2) % Mod_2;
Key_1 = (Key_1 + (int)(S[i] - 'a')) % Mod_1, Key_2 = (Key_2 + (int)(S[i] - 'a')) % Mod_2;
if(Ok(Key_1, Key_2))
++ans;
}
g << ans << '\n';
return 0;
}