fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll long long int
  7. #define mp make_pair
  8. #define eb emplace_back
  9. #define pb push_back
  10. #define len(v) ((ll)(v.size()))
  11. #define all(v) v.begin(),v.end()
  12. #define rall(v) v.rbegin(),v.rend()
  13. #define inp(a) for(auto &x:a) cin>>x;
  14. #define vll vector<ll>
  15. #define vvll vector<vector<ll>>
  16. #define vs vector<string>
  17. #define vchar vector<char>
  18. #define vvchar vector<vector<char>> 
  19. #define vpll vector<pair<ll,ll>> 
  20. #define mll map<ll,ll> 
  21. #define sll set<ll>
  22. #define pn cout<<"NO\n"
  23. #define py cout<<"YES\n"
  24. #define pll pair<ll,ll> 
  25. const ll MAX_SIZE = 100005;
  26. const ll ninf = (-1)*(1ll<<60);
  27. const ll inf = 1ll<<60;
  28. const ll mod = 1000000007;
  29. ll t[4*MAX_SIZE];
  30. template<typename T>
  31. void print(T t)
  32. {
  33.     for(const auto &e:t) cout<<e<<" ";
  34.     cout<<"\n";
  35. }
  36. ll fastpow(ll a ,ll b){
  37.     ll res=1;
  38.     while(b){
  39.        if(b&1) res=(res*a)%mod;
  40.        a=(a*a)%mod;
  41.        b/=2;
  42.     }
  43.     return res;
  44. }
  45. struct hashFunction
  46. {
  47.   size_t operator()(const pair<ll , 
  48.                     ll> &x) const
  49.   {
  50.     return x.first ^ x.second;
  51.   }
  52. };
  53.  
  54. ll p1=31,p2=67;
  55. ll inv1[MAX_SIZE];
  56. ll pt1[MAX_SIZE];
  57. ll inv2[MAX_SIZE];
  58. ll pt2[MAX_SIZE];
  59.  
  60. void solve(ll TC)
  61. {
  62.    ll n;
  63.    cin>>n;
  64.    vs v(n);
  65.    inp(v);
  66.    string s;
  67.    cin>>s;
  68.  
  69.    unordered_set<pll,hashFunction> m;
  70.    vll leng;
  71.    vll freq(1e5,0);
  72.  
  73.  
  74.    for(auto x:v){
  75.        ll hash_value1=0; 
  76.        ll hash_value2=0;
  77.        for(ll i=0;i<len(x);i++){
  78.           hash_value1=(hash_value1+pt1[i]*(x[i]-'a'+1))%mod;
  79.           hash_value2=(hash_value2+pt2[i]*(x[i]-'a'+1))%mod;
  80.        }
  81.        m.insert({hash_value1,hash_value2});
  82.        if(freq[len(x)]==0) leng.push_back(len(x));
  83.        freq[len(x)]=1;
  84.    }
  85.  
  86.    sort(all(leng));
  87.  
  88.  
  89.    vll hash1(len(s)+1,0),hash2(len(s)+1,0);
  90.  
  91.    for(ll i=1;i<=len(s);i++){
  92.        hash1[i]=(hash1[i-1]+pt1[i-1]*(s[i-1]-'a'+1))%mod;
  93.        hash2[i]=(hash2[i-1]+pt2[i-1]*(s[i-1]-'a'+1))%mod;
  94.    }
  95.  
  96.    vll dp(len(s)+1,0);
  97.    dp[0]=1;
  98.  
  99.    for(ll i=1;i<=len(s);i++){
  100.         for(auto l:leng){
  101.             if(l>i) break;
  102.             ll k1=((hash1[i]-hash1[i-l]+mod)*inv1[i-l])%mod;
  103.             ll k2=((hash2[i]-hash2[i-l]+mod)*inv2[i-l])%mod;
  104.             if(m.count({k1,k2})) dp[i]=(dp[i]+dp[i-l])%mod;
  105.         }            
  106.    }
  107.  
  108.    cout<<dp[len(s)]%mod<<endl;
  109.  
  110. }
  111.  
  112. int main()
  113. {
  114.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  115.  
  116.     ll Tc=1;
  117.     // cin>>Tc;
  118.     pt1[0]=1,pt2[0]=1;
  119.     inv1[0]=fastpow(1,mod-2);
  120.     inv2[0]=inv1[0];
  121.     ll k1=fastpow(p1,mod-2);
  122.     ll k2=fastpow(p2,mod-2);
  123.     for(ll i=1;i<MAX_SIZE;i++){
  124.         pt1[i]=(pt1[i-1]*p1)%mod;
  125.         inv1[i]=(inv1[i-1]*k1)%mod;
  126.         pt2[i]=(pt2[i-1]*p2)%mod;
  127.         inv2[i]=(inv2[i-1]*k2)%mod;
  128.     }
  129.  
  130.  
  131.     for(ll tc=1;tc<=Tc;tc++)
  132.     {
  133.         solve(tc);
  134.     }
  135.  
  136. return 0;
  137. }
  138. /*
  139. 1. Initialize all variables! Arrays etc.
  140. 2. Min of Max and Max of Min, such type of problems usually require Binary Search
  141. 3. Use to_string and stoi,atoi for conversions to suitable types.
  142. 4. For setting precision of n digits after decimal, use cout<<fixed;cout<<setprecision(n); before output, or at start of code if all outputs have same precision(include ios and iomanip header files.
  143. 5. Instead os using ceil(a/b), use (a+b-1)/b or (a-1)/b+1.
  144. 6. For char to int, subtract '0', for int to char add'0'
  145. */
Success #stdin #stdout 0.01s 8156KB
comments (?)
stdin
copy 
5
buda
tao
bud
at
ao
budatao
stdout
copy 
2
https://ideone.com/w04kLv
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!