Pagini recente » Cod sursa (job #827533) | Cod sursa (job #1819552) | Cod sursa (job #2514799) | Cod sursa (job #1925207) | Cod sursa (job #2296703)
#include<fstream>
#include<cstring>
#include<string>
#include<map>
#define P 3
#define F 100007
#define G 100021
using namespace std;
ifstream cin("abc2.in");
ofstream cout("abc2.out");
char a[10000005];
int hashing[2][50005];
int n,m,k,h1,h2,p1,p2;
map<string,int> M;
string b;
long long ans;
int main(){
cin>>a; ///cout<<a<<'\n';
n=strlen(a);
while(cin>>b){
///cout<<b<<'\n';
if(M[b]==0){
M[b]=1; ++m;
for(int i=0;b[i];i++){
hashing[0][m]=(hashing[0][m]*P+b[i])%F;
hashing[1][m]=(hashing[1][m]*P+b[i])%G;
}
}
}
k=b.size(); p1=p2=1;
///cout<<n<<' '<<m<<' '<<k<<'\n';
for(int i=1;i<k;i++){
p1=(p1*P)%F;
p2=(p2*P)%G;
}
for(int i=0;i<k;i++){
h1=(h1*P+a[i])%F;
h2=(h2*P+a[i])%G;
}
for(int i=1;i<=m;i++)
if(hashing[0][i]==h1 && hashing[1][i]==h2) ++ans;
for(int i=k;i<n;i++){
h1=((h1-(a[i-k]*p1)%F+F)*P+a[i])%F;
h2=((h2-(a[i-k]*p2)%G+G)*P+a[i])%G;
for(int j=1;j<=m;j++)
if(hashing[0][j]==h1 && hashing[1][j]==h2) ++ans;
}
cout<<ans;
}