Pagini recente » Cod sursa (job #508965) | Cod sursa (job #1740855)
#include <iostream>
#include <fstream>
#include <unordered_map>
#define MOD 666013
#define MOD1 100007
#define NMAX 1000001
#define CMAX 21
#define DMAX 50001
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
char s[NMAX];
char q[CMAX];
int m1[MOD],m2[MOD];
int x,a[NMAX],d1[DMAX],d2[NMAX],c,n,p,cuv,p1=1,p2=1,h1,h2,contor;
int main()
{
in >> s;
for(n=0;s[n]!='\0';n++)
{
a[n] = s[n]-'a'+1;
}
while(in >> q)
{
for(cuv=0;q[cuv]!='\0';cuv++)
{
//cout << p << " ";
d1[c] = (d1[c]*3+(q[cuv]-'a'+1))%MOD;
d2[c] = (d2[c]*3+(q[cuv]-'a'+1))%MOD1;
}
c++;
}
for(int i=0;i<cuv;i++)
{
h1 = (h1*3 + a[i])%MOD;
h2 = (h2*3 + a[i])%MOD1;
p1 = (3*p1)%MOD;
p2 = (3*p2)%MOD1;
}
p1 /=3;
p2 /=3;
m1[h1] = 1;
m2[h2] = 1;
for(int i=cuv;i<n;i++)
{
h1 = ((h1-(h1/p1)*p1)*3+ a[i])%MOD;
h2 = ((h2-(h2/p2)*p2)*3+ a[i])%MOD;
m1[h1]++;
m2[h2]++;
}
int contor=0;
for(int i=0;i<c;i++)
{
// cout <<m[d[i]] << " ";
if(m1[d1[i]]>0)
{
contor+=m1[d1[i]];
m1[d1[i]] =0;
}
}
out << contor;
return 0;
}