fork download
copy 
  1. // ﷽
  2. // Contest: string (medium)
  3. //
  4. // Judge: Codeforces
  5. // URL: https://c...content-available-to-author-only...s.com/group/o09Gu2FpOx/contest/559867/problem/C
  6. // Memory Limit: 512
  7. // Time Limit: 10000
  8. // Start: Thu 08 May 2025 12:25:56 AM EEST
  9. #include <bits/stdc++.h>
  10.  
  11. #ifdef ALGOAT
  12. #include "debug.hpp"
  13. #else
  14. #define debug(...) 0
  15. #define debug_itr(...) 0
  16. #define debug_bits(...) 0
  17. #endif
  18.  
  19. // 48-57 -> 0-9  65-90 -> A-Z 97-122 -> a-z
  20. #define fastio()                                                               \
  21.   ios_base::sync_with_stdio(false);                                            \
  22.   cin.tie(NULL);
  23.  
  24. #define int long long
  25. #define F first
  26. #define S second
  27. #define all(a) (a).begin(), (a).end()
  28. #define rall(a) (a).rbegin(), (a).rend()
  29. #define rep(i, a, b) for (int i = (a); i < (b); ++i)
  30. #define sz(x) (int)(x).size()
  31. #define vi vector<int>
  32.  
  33. /*template <class T> using rpq = priority_queue<T, vector<T>, greater<T>>;*/
  34.  
  35. const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1},
  36.           dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
  37.  
  38. using namespace std;
  39. constexpr int H = 2;
  40. typedef array<long long, H> val;
  41. vector<val> B;
  42. const val M = {
  43.     1000000007, 1444444447,
  44.     // 998244353,
  45.     // 1000000009,
  46. };
  47.  
  48. val tmp;
  49.  
  50. val operator*(const val &a, const val &b) {
  51.   for (int i = 0; i < H; i++)
  52.     tmp[i] = a[i] * b[i] % M[i];
  53.   return tmp;
  54. }
  55.  
  56. val operator-(const val &a, const val &b) {
  57.   for (int i = 0; i < H; i++)
  58.     tmp[i] = (a[i] - b[i] + M[i]) % M[i];
  59.   return tmp;
  60. }
  61.  
  62. val operator+(const val &a, const val &b) {
  63.   for (int i = 0; i < H; i++)
  64.     tmp[i] = (a[i] + b[i]) % M[i];
  65.   return tmp;
  66. }
  67.  
  68. val getval(int x) {
  69.   for (int i = 0; i < H; i++)
  70.     tmp[i] = x % M[i];
  71.   return tmp;
  72. }
  73.  
  74. void setB(int n) {
  75.   if (B.size() == 0) {
  76.     mt19937 rng(random_device{}());
  77.     B.assign(2, getval(1));
  78.     for (int i = 0; i < H; i++)
  79.       B.back()[i] = uniform_int_distribution<int>(1, M[i] - 1)(rng);
  80.   }
  81.   while ((int)B.size() <= n)
  82.     B.push_back(B.back() * B[1]);
  83. }
  84.  
  85. struct Hash {
  86.   vector<val> h;
  87.  
  88.   Hash(const string &s) : Hash(vector<int>(s.begin(), s.end())) {}
  89.  
  90.   Hash(const vector<int> &s) {
  91.     vector<val> v;
  92.     for (auto x : s)
  93.       v.push_back(getval(x));
  94.     *this = Hash(v);
  95.   }
  96.  
  97.   Hash(const vector<val> &s) : h(s.size() + 1) {
  98.     setB(s.size());
  99.     for (int i = 0; i < (int)s.size(); i++)
  100.       h[i + 1] = h[i] * B[1] + s[i];
  101.   }
  102.  
  103.   val get(int l, int r) { return h[r + 1] - h[l] * B[r - l + 1]; }
  104. };
  105. struct ValHash {
  106.   size_t operator()(const val &v) const {
  107.     size_t h = 0;
  108.     for (int i = 0; i < H; ++i) {
  109.       h ^= std::hash<long long>()(v[i]) + 0x9e3779b9 + (h << 6) + (h >> 2);
  110.     }
  111.     return h;
  112.   }
  113. };
  114.  
  115. void solve() {
  116.   int q;
  117.   cin >> q;
  118.   vector<string> words(q);
  119.   for (auto &w : words)
  120.     cin >> w;
  121.  
  122.   unordered_map<int, unordered_set<val, ValHash>> dict;
  123.   set<int> word_lengths;
  124.   for (const auto &w : words) {
  125.     int len = w.size();
  126.     word_lengths.insert(len);
  127.     dict[len].insert(Hash(w).get(0, len - 1));
  128.   }
  129.  
  130.   string s;
  131.   cin >> s;
  132.   int n = s.size();
  133.   Hash hs(s);
  134.  
  135.   const int INF = INT_MAX / 2;
  136.   vector<int> dp(n + 2, INF);
  137.   dp[n + 1] = 0;
  138.  
  139.   for (int i = n; i >= 1; --i) {
  140.     for (int len : word_lengths) {
  141.       if (i + len - 1 > n)
  142.         break;
  143.       val h = hs.get(i - 1, i + len - 2);
  144.       if (dict[len].count(h)) {
  145.         dp[i] = min(dp[i], dp[i + len] + 1);
  146.       }
  147.     }
  148.   }
  149.  
  150.   cout << (dp[1] >= INF ? -1 : dp[1]) << "\n";
  151. }
  152.  
  153. int32_t main() {
  154.   /*freopen("whereami.in", "r", stdin);*/
  155.   /*freopen("whereami.out", "w", stdout);*/
  156.   fastio();
  157.   int n = 1;
  158.  
  159. #ifdef MUTLI_CASE
  160.   cin >> n;
  161. #endif
  162.   while (n--)
  163.     solve();
  164.   return 0;
  165. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/LA9I3B
Hash
language:
C++14 (gcc 8.3)
created:
3 days 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!