fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 1e5 + 5;
  5. const int base = 331;
  6. const int mod = 1e9 + 7;
  7. const int mod1 = 1e9 + 2277;
  8. const int mod2 = 1e9 + 5277;
  9. //
  10. int n;
  11. int dp[mx] = {1};
  12. vector<int> len;
  13. unordered_set<int> S1[mx], S2[mx];
  14. long long h1[mx], p1[mx] = {1};
  15. long long h2[mx], p2[mx] = {1};
  16. string T;
  17. //
  18. int hashing1 (void)
  19. {
  20.     long long hash_value = 0;
  21.     //
  22.     for (char c : T)
  23.         hash_value = (hash_value * base + c) % mod1;
  24.     return hash_value;
  25. }
  26. int hashing2 (void)
  27. {
  28.     long long hash_value = 0;
  29.     //
  30.     for (char c : T)
  31.         hash_value = (hash_value * base + c) % mod2;
  32.     return hash_value;
  33. }
  34. int get1 (int l, int r)
  35. {
  36.     return (h1[r] - h1[l] * p1[r - l] + 1LL * mod1 * mod1) % mod1;
  37. }
  38. int get2 (int l, int r)
  39. {
  40.     return (h2[r] - h2[l] * p2[r - l] + 1LL * mod2 * mod2) % mod2;
  41. }
  42. inline void add (int &a, int b)
  43. {
  44.     a += b;
  45.     if (a >= mod)
  46.         a -= mod;
  47. }
  48. //
  49. void process (void)
  50. {
  51.     for (cin >> n; n--;)
  52.     {
  53.         cin >> T;
  54.         S1[T.size()].insert(hashing1());
  55.         S2[T.size()].insert(hashing2());
  56.     }
  57.     cin >> T;
  58.     n = T.size();
  59.     for (int i = 1; i <= n; ++i)
  60.     {
  61.         p1[i] = p1[i - 1] * base % mod1;
  62.         h1[i] = (h1[i - 1] * base + T[i - 1]) % mod1;
  63.         p2[i] = p2[i - 1] * base % mod2;
  64.         h2[i] = (h2[i - 1] * base + T[i - 1]) % mod2;
  65.     }
  66.  
  67.     for (int i = 1; i <= n; ++i)
  68.         if (!S1[i].empty())
  69.             len.emplace_back(i);
  70.     for (int i = 1; i <= n; ++i)
  71.         for (int j : len)
  72.         {
  73.             if (j > i)
  74.                 break;
  75.             if (S1[j].find(get1(i - j, i)) != S1[j].end() &&
  76.                 S2[j].find(get2(i - j, i)) != S2[j].end())
  77.                 add(dp[i], dp[i - j]);
  78.         }
  79.  
  80.     cout << dp[n];
  81. }
  82. //
  83. signed main (void)
  84. {
  85.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  86.     process();
  87. }
Success #stdin #stdout 0.01s 14672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/pH5NVm
https://m...content-available-to-author-only...j.com/problem/553
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

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!