Pagini recente » Cod sursa (job #2497932) | Cod sursa (job #2298687) | Cod sursa (job #1429267) | Cod sursa (job #2908148) | Cod sursa (job #1845913)
#include<fstream>
#include<cstring>
#include<unordered_set>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int MOD[] = {666013,int(1e9)+7};
const int Base = 37;
const int Nmax = 10000001;
char s[Nmax],cuv[21];
int n,let[2][30];
long long g;
unordered_set<int> W[666013];
int main(){
in.getline(s,Nmax);
while(!in.eof()){
in.getline(cuv,21);
if(in.eof()) break;
pair<int,int> has={0,0};
n=strlen(cuv);
for(int i=0;i<n;i++){
has.first = (1LL*has.first*37 + cuv[i] - 'a')%MOD[0];
has.second = (1LL*has.second*37 + cuv[i] - 'a')%MOD[1];
}
W[has.first].insert(has.second);
}
pair<int,int> pw={1,1};
for(int i=1;i<n;i++){
pw.first = (1LL*pw.first*37)%MOD[0];
pw.second = (1LL*pw.second*37)%MOD[1];
}
for(char z='a';z<='z';z++){
let[0][z-'a']=(1LL*(z-'a')*pw.first)%MOD[0];
let[1][z-'a']=(1LL*(z-'a')*pw.second)%MOD[1];
}
int sz=strlen(s),ans=0;
pair<int,int> has={0,0};
for(int i=0;i<sz;i++){
if(i>=n){
if(W[has.first].find(has.second)!=W[has.first].end()) ans++;
g = 1LL*MOD[0] + has.first - let[0][s[i-n]-'a']; while(g>MOD[0]) g-=MOD[0]; has.first = g;
g = 1LL*MOD[1] + has.second - let[1][s[i-n]-'a']; while(g>MOD[1]) g-=MOD[1]; has.second = g;
}
g = 37LL*has.first + s[i] - 'a'; while(g>MOD[0]) g-=MOD[0]; has.first = g;
g = 37LL*has.second + s[i] - 'a'; while(g>MOD[1]) g-=MOD[1]; has.second = g;
}
if(W[has.first].find(has.second)!=W[has.first].end()) ans++;
out<<ans<<'\n';
return 0;
}