Pagini recente » Cod sursa (job #1293825) | Cod sursa (job #713882) | Cod sursa (job #1645503) | Cod sursa (job #248538) | Cod sursa (job #2004128)
#include <fstream>
#include <algorithm>
#include <vector>
#define MOD1 30103
#define MOD2 666013
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int N, M, i, j, ANS;
int P1, P2, nr1, nr2;
vector <int> Hash[MOD1];
string T, P;
void Check(int A, int B)
{
if (find(Hash[A].begin(), Hash[A].end(), B)!=Hash[A].end())
ANS++;
}
int main()
{
fin >> T;
N=T.size();
while (fin >> P)
{
M=P.size();
nr1=nr2=0;
P1=P2=1;
for (i=M-1; i>=0; i--)
{
nr1+=P1*(P[i]-'a');
nr1%=MOD1;
nr2+=P2*(P[i]-'a');
nr2%=MOD2;
if (i>0)
{
P1*=3;
P1%=MOD1;
P2*=3;
P2%=MOD2;
}
}
Hash[nr1].push_back(nr2);
}
nr1=nr2=0;
P1=P2=1;
for (i=M-1; i>=0; i--)
{
nr1+=P1*(T[i]-'a');
nr1%=MOD1;
nr2+=P2*(T[i]-'a');
nr2%=MOD2;
if (i>0)
{
P1*=3;
P1%=MOD1;
P2*=3;
P2%=MOD2;
}
}
Check(nr1, nr2);
for (i=M; i<N; i++)
{
nr1-=P1*(T[i-M]-'a');
nr1%=MOD1;
if (nr1<0)
nr1=MOD1+nr1;
nr1*=3;
nr1+=T[i]-'a';
nr1%=MOD1;
nr2-=P2*(T[i-M]-'a');
nr2%=MOD2;
if (nr2<0)
nr2=MOD2+nr2;
nr2*=3;
nr2+=T[i]-'a';
nr2%=MOD2;
Check(nr1, nr2);
}
fout << ANS << '\n';
fin.close();
fout.close();
return 0;
}