Pagini recente » Cod sursa (job #216267) | Cod sursa (job #1150586) | Cod sursa (job #124687) | Cod sursa (job #2028420) | Cod sursa (job #1490788)
#include <fstream>
#include <bitset>
#include <cstring>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#define nmax 50005
#define lmax 10000005
#define kmax 22
#define mod1 200005
#define mod2 1000023
using namespace std;
int n,m,mc,sol,t1,t2,h1,h2;
char s[lmax],a[kmax];
char buffer[lmax/5];
vector<long long> v[mod1];
void hashins(int t1,int t2)
{
v[t1].push_back(t2);
}
int hashexist(int t1,int t2)
{
for (int i=0;i<v[t1].size();i++)
if (v[t1][i]==t2)
return 1;
return 0;
}
int main()
{
int i,j;
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
scanf("%s",&s);
n=strlen(s);
while (scanf("%s",&a)==1) {
m=strlen(a);
if (m) mc=m;
t1=0;t2=0;
for (i=0;a[i];i++) {
t1=(1LL*t1*3+a[i]-'a')%mod1;
t2=(1LL*t2*3+a[i]-'a')%mod2;
}
hashins(t1,t2);
}
m=mc;
t1=0;t2=0;h1=1;h2=1;
for (i=0;i<m;i++) {
t1=(1LL*t1*3+s[i]-'a')%mod1;
t2=(1LL*t2*3+s[i]-'a')%mod2;
}
for (i=1;i<m;i++) {
h1=(1LL*h1*3)%mod1;
h2=(1LL*h2*3)%mod2;
}
for (i=m;i<=n;i++) {
if (hashexist(t1,t2))
sol++;
t1=(1LL*t1-h1*(s[i-m]-'a')+2*mod1);
t2=(1LL*t2-h2*(s[i-m]-'a')+2*mod2);
t1=((1LL*t1*3+s[i]-'a')+2*mod1)%mod1;
t2=((1LL*t2*3+s[i]-'a')+2*mod2)%mod2;
}
printf("%d\n",sol);
return 0;
}