Pagini recente » Cod sursa (job #2769629) | Cod sursa (job #1427384) | Cod sursa (job #1165269) | Cod sursa (job #3225671) | Cod sursa (job #2260537)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
const int Nmax = 10000005;
const int P = 100003;
const int P1 = 92347;
char sir[Nmax + 5];
char a[50005][55];
int n, La, Lsir;
vector < int > L[P];
inline bool Ok(int H, int H1)
{
int r;
r = H % P;
for(auto it : L[r])
if(it == H1)
return true;
return false;
}
int main()
{
int sol = 0;
unsigned int p , H , H1 , p1;
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'));
H1 = (H1 * 3 + (a[i][j] - 'a'));
}
if(!Ok(H, H1))
L[H % P] . push_back(H1 % P1);
}
H = H1 = 0;
p = p1 = 1;
for(int i = 1 ; i <= La ; i++)
{
H = (H * 3 + (sir[i] - 'a'));
H1 = (H1 * 3 + (sir[i] - 'a'));
if(i > 1)
{
p = (p * 3);
p1 = (p1 * 3);
}
}
sol += Ok(H, H1 % P1);
///cout << p << " " << p1 << "\n";
for(int i = La + 1; i <= Lsir ; i++)
{
H = ((H - (sir[i - La] - 'a') * p) * 3 + (sir[i] - 'a'));
H1 = ((H1 - (sir[i - La] - 'a') * p1) * 3 + (sir[i] - 'a'));
///cout << H << " " << H1 << "\n";
sol += Ok(H, H1 % P1);
}
fout << sol << "\n";
fin.close();
fout.close();
return 0;
}