Pagini recente » Cod sursa (job #1769962) | Cod sursa (job #1684088) | Cod sursa (job #3285502) | Cod sursa (job #1519279) | Cod sursa (job #2260519)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
const int Nmax = 10000005;
const int P = 123457;
const int P1 = 92347;
char sir[Nmax + 5];
char a[50005][55];
int n, La, Lsir;
vector < int > L[P];
int main()
{
int p, H, sol = 0, H1, p1;
bool ok;
fin >> (sir + 1);
Lsir = strlen(sir + 1);
while(fin >> (a[++n] + 1))
;
n--;
La = strlen(a[1] + 1);
if(La > Lsir)
{
fout << "0\n";
return 0;
}
for(int i = 1 ; i <= n ; i++)
{
H = H1 = 0;
for(int j = 1 ; j <= La ; j++)
{
H = (H * 3 + (a[i][j] - 'a')) % P;
H1 = (H1 * 3 + (a[i][j] - 'a')) % P1;
}
ok = false;
for(auto it : L[H])
if(it == H1)
{
ok = true;
break;
}
if(!ok)
L[H] . push_back(H1);
}
H = H1 = 0;
p = p1 = 1;
for(int i = 1 ; i <= La ; i++)
{
H = (H * 3 + (sir[i] - 'a')) % P;
H1 = (H1 * 3 + (sir[i] - 'a')) % P1;
if(i > 1)
{
p = (p * 3) % P;
p1 = (p1 * 3) % P1;
}
}
ok = false;
for(auto it : L[H])
if(it == H1)
{
ok = true;
break;
}
sol += ok;
///cout << p << " " << p1 << "\n";
for(int i = La + 1; i <= Lsir ; i++)
{
H = (((H - (sir[i - La] - 'a') * p) % P + P) * 3 + (sir[i] - 'a')) % P;
H1 = (((H1 - (sir[i - La] - 'a') * p1) % P1 + P1) * 3 + (sir[i] - 'a')) % P1;
///cout << H << " " << H1 << "\n";
ok = false;
for(auto it : L[H])
if(it == H1)
{
ok = true;
break;
}
sol += ok;
}
fout << sol << "\n";
fin.close();
fout.close();
return 0;
}