Pagini recente » Cod sursa (job #473800) | Cod sursa (job #2853821) | Cod sursa (job #2580414) | Cod sursa (job #2486971) | Cod sursa (job #2260495)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
const int Nmax = 10000005;
const int P = 123457;
char sir[Nmax + 5];
char a[50005][55];
int n , La , Lsir;
unordered_map < int , bool > M;
vector < int > L[P];
int main()
{
int p = 1 , H = 0 , r , sol = 0;
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 <= La ; i++)
{
H = (H * 3 + (sir[i] - 'a')) % P;
if(i > 1)
p = (p * 3) % P;
}
r = H % P;
L[r] . push_back(1);
for(int i = La + 1 ; i <= Lsir ; i++)
{
H = (((H - (sir[i - La] - 'a') * p) % P + P) * 3 + (sir[i] - 'a')) % P;
r = H % P;
L[r] . push_back(i - La + 1);
}
for(int i = 1 ; i <= n ; i++)
{
H = 0;
for(int j = 1 ; j <= La ; j++)
H = (H * 3 + (a[i][j] - 'a')) % P;
r = H % P;
for(auto it : L[r])
if(!M[it])
{
sol++;
M[it] = true;
}
}
fout << sol << "\n";
fin.close();
fout.close();
return 0;
}