Segment Tree DP + Rolling Hash & Binary Search Update
Approach\n\nWe compute the rolling hash for everything in words as well as target. Let dp[i] be the minimum amount of strings to make target[i..target.length-1]
# Approach\n\nWe compute the rolling hash for everything in $$words$$ as well as $$target$$. Let $$dp[i]$$ be the minimum amount of strings to make $$target[i..target.length-1]$$. We need to update the DP in an efficient way.\n\nFor each $$i \\ s.t. \\ 0<=i<|target|$$, let $$r$$ be the maximum number of characters starting at $$target[i]$$ that matches some prefix of a word in $$words$$. We can take the minimum DP value in $$dp[i+1..i+r]$$ (by using a range query structure).\n\nWe can compute $$r$$ by going through all the words for a fixed $$dp[i]$$, then we can apply binary search for the length of the current word. We can use rolling hash to speed up the substring comparison.\n\n#### Time Complexity: $$O(|target|*|words|*log(|words|))$$\n\n---\n\n# Explained Solution\n\n```cpp []\nstruct rolling_hash {\n  static constexpr unsigned long long M = (1ULL << 61) - 1, P = 257;\n  inline static vector<unsigned long long> p = vector<unsigned long long>{1};\n  vector<unsigned long long> h;\n  rolling_hash(const string &s) {\n    int n = s.size();\n    h.resize(n + 1);\n    for (unsigned long long i = p.size(), pp = p.back(); i <= n; i++)\n      p.push_back(pp = __uint128_t(pp) * P % M);\n    for (int i = n - 1; i >= 0; i--)\n      h[i] = (s[i] + __uint128_t(h[i + 1]) * P % M) % M;\n  }\n  unsigned long long hash(int l, int r) {\n    return (h[l] - __uint128_t(h[r + 1]) * p[r - l + 1] % M + M) % M;\n  }\n};\n\ntemplate <typename T, typename A, typename C, typename C2 = C, typename F = identity>\nstruct segment_tree {\n  vector<T> tree;\n  A apply;\n  C combine;\n  C2 query_combine;\n  F query_fn;\n  segment_tree(int n, T v, A apply, C combine, C2 query_combine = {}, F query_fn = {}) : tree(2 * n, v), apply(apply), combine(combine), query_combine(query_combine), query_fn(query_fn) {\n    for (int i = n - 1; i > 0; --i)\n      tree[i] = combine(tree[i << 1], tree[i << 1 | 1]);\n  }\n  template <typename... Args>\n  void update(int i, Args &&...args) {\n    int n = tree.size() >> 1;\n    for (apply(tree[i += n], std::forward<Args>(args)...); i >>= 1;)\n      tree[i] = combine(tree[i << 1], tree[i << 1 | 1]);\n  }\n  template <typename R = T, typename... Args>\n  R query(int l, int r, R ans = {}, Args &&...args) { // [l, r)\n    int n = tree.size() >> 1;\n    auto ansl = ans, ansr = ans;\n    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {\n      if (l & 1)\n        ansl = query_combine(ansl, query_fn(tree[l++], std::forward<Args>(args)...));\n      if (r & 1)\n        ansr = query_combine(query_fn(tree[--r], std::forward<Args>(args)...), ansr);\n    }\n    return query_combine(ansl, ansr);\n  }\n};\n\nclass Solution {\npublic:\n  int minValidStrings(vector<string> &w, string t) {\n    int n = w.size(), m = t.size();\n    rolling_hash rh_t(t);\n    vector<rolling_hash> rh_w;\n    for (int i = 0; i < n; i++) {\n      rh_w.emplace_back(w[i]);\n    }\n    auto apply = [](int &x, int y) {\n      x = min(x, y);\n    };\n    auto comb = [](int x, int y) {\n      return min(x, y);\n    };\n    segment_tree dp(m + 1, (int)1e9, apply, comb);\n    dp.update(m, 0);\n    for (int i = m - 1; i >= 0; i--) {\n      int r = 0;\n      for (int j = 0; j < n; j++) {\n        int lb = 0, rb = min((int)w[j].size(), m - i) + 1;\n        while (rb - lb > 1) {\n          int mb = (lb + rb) / 2;\n          if (rh_w[j].hash(0, mb - 1) == rh_t.hash(i, i + mb - 1)) {\n            r = max(r, mb);\n            lb = mb;\n          } else {\n            rb = mb;\n          }\n        }\n      }\n      dp.update(i, dp.query(i, i + r + 1, (int)1e9) + 1);\n    }\n    int x = dp.query(0, 1, (int)1e9);\n    return x == 1e9 ? -1 : x;\n  }\n};\n```\n\n---\n\n# Optimal Solution\n\n```cpp\nstruct rolling_hash {\n  static constexpr uint64_t M = (1ULL << 61) - 1, P = 257;\n  inline static vector<uint64_t> p = vector<uint64_t>{1};\n  vector<uint64_t> h;\n  rolling_hash(const string &s) {\n    int n = s.size();\n    h.resize(n + 1);\n    for (uint64_t i = p.size(), pp = p.back(); i <= n; i++)\n      p.push_back(pp = __uint128_t(pp) * P % M);\n    for (int i = n - 1; i >= 0; i--)\n      h[i] = (s[i] + __uint128_t(h[i + 1]) * P % M) % M;\n  }\n  uint64_t hash(int l, int r) {\n    return (h[l] - __uint128_t(h[r + 1]) * p[r - l + 1] % M + M) % M;\n  }\n};\n\nclass Solution {\npublic:\n  int minValidStrings(vector<string> &w, string t) {\n    int n = w.size(), m = t.size();\n    unordered_set<uint64_t> hs;\n    for (int i = 0; i < n; i++) {\n      rolling_hash rh(w[i]);\n      for (int j = 0; j < w[i].size(); j++) {\n        hs.insert(rh.hash(0, j));\n      }\n    }\n    rolling_hash rh(t);\n    vector z(m, 0);\n    for (int i = 0, j = 0; i < m; i++) {\n      for (j = max(j, i); j < m && hs.count(rh.hash(i, j)); j++) {\n      }\n      z[i] = hs.count(rh.hash(i, j - 1)) ? j - i : 0;\n    }\n    int ans = 0, next = 0, far = 0;\n    for (int i = 0; i <= next && far < m;) {\n      int i2 = i;\n      for (; i <= next; i++) {\n        far = max(far, i + z[i]);\n      }\n      if (far <= next) {\n        return -1;\n      }\n      next = far;\n      ans++;\n    }\n    return ans;\n  }\n};\n```
['Binary Search', 'Dynamic Programming', 'Segment Tree', 'Rolling Hash', 'C++']