fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void _print() { cerr << "]" << endl; }
  5. template<typename T, typename... V>
  6. void _print(T t, V... v) { cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...); }
  7.  
  8. //#define LOCAL
  9. #ifdef LOCAL
  10.   #define dbg(x...) cerr << "[" << #x << "]: ["; _print(x)
  11. #else
  12.   #define dbg(x...)
  13.   #define endl '\n'
  14. #endif
  15.  
  16. #define pb push_back
  17. #define ff first
  18. #define ss second
  19. #define sz(x) int(x.size())
  20. #define all(x) x.begin(), x.end()
  21. #define forn(i, n) for (int i = 0; i < n; ++i)
  22. #define forne(i, n) for (int i = 0; i <= n; ++i)
  23. #define rforn(i, n) for (int i = n-1; i >= 0; --i)
  24. #define forab(i, a, b) for (int i = a; i < b; ++i)
  25. #define forabe(i, a, b) for (int i = a; i <= b; ++i)
  26. #define form(i, n, m, x) for (int i = n; i < m; i += x)
  27. #define rform(i, n, m, x) for (int i = n; i >= m; i -= x)
  28.  
  29. typedef long long ll;
  30. typedef pair<int, int> ii;
  31. typedef vector<int> vi;
  32.  
  33. const ll mod = 1000000007;
  34. const ll p = 257;
  35. ll power[100002];
  36.  
  37. void pre(){
  38.     power[0] = 1;
  39.     forab(i, 1, 100002){
  40.         power[i] = (power[i-1] * p) % mod;
  41.     }
  42. }
  43.  
  44. ll get_hash(string &s){
  45.     ll h = 0;
  46.     forn(i, sz(s)){
  47.         h = (h + (s[i] * power[i])) % mod;
  48.     }
  49.     return h;
  50. }
  51.  
  52. vector<string> words;
  53. vector<ll> hwords;
  54.  
  55. string s;
  56.  
  57. struct node{
  58.     int len;
  59.     ll h;
  60.  
  61.     node(){}
  62.     node(int _l, ll _h){
  63.         len = _l;  h = _h;
  64.     }
  65. };
  66.  
  67. struct STree {
  68.     int n; vector<node> st;
  69.     node neutro = node(0, 0);
  70.  
  71.     STree(){}
  72.  
  73.     void build(string &a) {
  74.         n = sz(a);
  75.         st.resize(n * 4);
  76.         build(1, 0, n - 1, a);
  77.     }
  78.  
  79.     node oper(node a, node b) {
  80.         node n = node(a.len + b.len, (a.h+b.h*power[a.len]) % mod);
  81.         return n;
  82.     }
  83.  
  84.     void build(int v, int tl, int tr, string &a) {
  85.         if(tl == tr) {
  86.             st[v] = node(1, a[tl]);
  87.             return;
  88.         }
  89.         int tm = (tr + tl) / 2;
  90.         build(v * 2, tl, tm, a);
  91.         build(v * 2 + 1, tm + 1, tr, a);
  92.         st[v] = oper(st[v * 2], st[v * 2 + 1]);
  93.     }
  94.  
  95.     node query(int v, int tl, int tr, int l, int r) {
  96.         if(tl > r || tr < l) return neutro;
  97.         if(l <= tl && tr <= r) return st[v];
  98.         int tm = (tl + tr) / 2;
  99.         return oper(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r));
  100.     }
  101.  
  102.     ll query(int l, int r) { return query(1, 0, n - 1, l, r).h; }
  103. };
  104.  
  105. int n;
  106. int memo[100002];
  107. STree st;
  108.  
  109. int dp(int i){
  110.     if(i >= sz(s)) return 1;
  111.     if(memo[i] != -1) return memo[i];
  112.     //dbg(i);
  113.  
  114.     int ans = 0;
  115.     forn(k, n){
  116.         //ll h = st.query(i, i+sz(words[k])-1);
  117.         //dbg("#", hwords[k], h, i, i+sz(words[k])-1);
  118.         if(hwords[k] == st.query(i, i+sz(words[k])-1)){
  119.             ans = (ans + dp(i + sz(words[k]))) % mod;
  120.         }
  121.     }
  122.     return memo[i] = ans;
  123. }
  124.  
  125. int main() {
  126.     ios_base::sync_with_stdio(false);
  127.     cin.tie(0);
  128.     pre();
  129.  
  130.     while(cin >> n){
  131.         words.clear();
  132.         hwords.clear();
  133.  
  134.         string x;
  135.         forn(i, n){
  136.             cin >> x;
  137.             words.pb(x);
  138.             hwords.pb(get_hash(x));
  139.         }
  140.  
  141.         cin >> s;
  142.         st.build(s);
  143.  
  144.         memset(memo, -1, sizeof memo);
  145.         int res = dp(0);
  146.         cout << res << '\n';
  147.     }
  148.  
  149.     return 0;
  150. }
  151.  
  152.  
  153.  
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin 
5
buda
tao
bud
at
ao
budatao
stdout 
2
https://ideone.com/8JjUIG
language:
C++ (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!