My Solutions
1. Use the z-function\n\n/**\n * Time Complexity: O(n_characters + n_words * n_target)\n * Space Complexity: O(n_word + n_target)\n * where `n_characters` is th
**1. Use the `z-function`**\n```\n/**\n * Time Complexity: O(n_characters + n_words * n_target)\n * Space Complexity: O(n_word + n_target)\n * where `n_characters` is the sum of the length of each string of the vector `words`\n *       `n_word` is the maximum length of the strings of the vector `words`\n *       `n_words` is the length of the vector `words`\n *       `n_target` is the length of the string `target`\n */\nclass Solution {\n public:\n  int minValidStrings(const vector<string> &words, const string &target) {\n    constexpr char separator = \'#\';\n    const int n_target = static_cast<int>(target.size());\n    int jump[n_target];\n    memset(jump, 0, sizeof(jump));\n    for (const string &word : words) {\n      const int n_word = static_cast<int>(word.size());\n      const string s(word + separator + target);\n      const int n = static_cast<int>(s.size());\n      int z[n];\n      memset(z, 0, sizeof(z));\n      int l = 0;\n      int r = 0;\n      for (int i = 1; i < n; ++i) {\n        if (i < r) {\n          z[i] = min(z[i - l], r - i);\n        }\n        for (; i + z[i] < n && s[i + z[i]] == s[z[i]]; ++z[i]) {\n        }\n        if (i > n_word) {\n          jump[i - n_word - 1] = max(jump[i - n_word - 1], z[i]);\n        }\n        if (i + z[i] > r) {\n          l = i;\n          r = i + z[i];\n        }\n      }\n    }\n\n    int ret = 0;\n    for (int max_reach = 0, next_max_reach = 0, i = 0; i < n_target && max_reach < n_target; ++i) {\n      next_max_reach = max(next_max_reach, i + jump[i]);\n      if (i == max_reach) {\n        if (next_max_reach == max_reach) {\n          ret = -1;\n          break;\n        }\n        ++ret;\n        max_reach = next_max_reach;\n      }\n    }\n    return ret;\n  }\n};\n```\n**2. Use the `KMP` algorithm**\n```\n/**\n * Time Complexity: O(n_characters + n_words * n_target)\n * Space Complexity: O(n_word + n_target)\n * where `n_characters` is the sum of the length of each string of the vector `words`\n *       `n_word` is the maximum length of the strings of the vector `words`\n *       `n_words` is the length of the vector `words`\n *       `n_target` is the length of the string `target`\n */\nclass Solution {\n public:\n  int minValidStrings(const vector<string> &words, const string &target) {\n    constexpr char separator = \'#\';\n    const int n_target = static_cast<int>(target.size());\n    int jump[n_target];\n    memset(jump, 0, sizeof(jump));\n    for (const string &word : words) {\n      const int n_word = static_cast<int>(word.size());\n      const string s(word + separator + target);\n      const int n = static_cast<int>(s.size());\n      int next[n + 1];\n      memset(next, 0, sizeof(next));\n      next[0] = -1;\n      int i = 0;\n      int j = -1;\n      while (i < n) {\n        if (j == -1 || s[i] == s[j]) {\n          ++i;\n          ++j;\n          next[i] = j;\n        } else {\n          j = next[j];\n        }\n      }\n      for (int i = 1; i < n_target + 1; ++i) {\n        const int length = max(0, next[n_word + 1 + i]);\n        if (length != 0) {\n          jump[i - length] = max(jump[i - length], length);\n        }\n      }\n    }\n\n    int ret = 0;\n    for (int max_reach = 0, next_max_reach = 0, i = 0; i < n_target && max_reach < n_target; ++i) {\n      next_max_reach = max(next_max_reach, i + jump[i]);\n      if (i == max_reach) {\n        if (next_max_reach == max_reach) {\n          ret = -1;\n          break;\n        }\n        ++ret;\n        max_reach = next_max_reach;\n      }\n    }\n    return ret;\n  }\n};\n```\n**3. Use the `Aho-Corasick Automation`**\n```\n/**\n * Time Complexity: O(n_characters + n_target)\n * Space Complexity: O(n_characters + n_target)\n * where `n_characters` is the sum of the length of each string of the vector `words`\n *       `n_target` is the length of the string `target`\n */\nclass Solution {\n private:\n  static constexpr int letters = 26;\n  static constexpr char a = \'a\';\n  \n  class AcaNode {\n   public:\n    AcaNode() : children_{}, fail_{}, depth_{} {\n    }\n    \n    ~AcaNode() {\n      for (AcaNode * const child : children_) {\n        delete child;\n      }\n    }\n    \n    AcaNode* get_or_create_child(const char c) {\n      AcaNode *&ret = children_[c - a];\n      if (ret == nullptr) {\n        ret = new AcaNode();\n      }\n      return ret;\n    }\n    \n    AcaNode* get_child(const char c) const {\n      return children_[c - a];\n    }\n    \n    AcaNode* fail() const {\n      return fail_;\n    }\n    \n    void set_fail(AcaNode * const fail) {\n      fail_ = fail;\n    }\n    \n    int depth() const {\n      return depth_;\n    }\n    \n    void set_depth(const int depth) {\n      depth_ = depth;\n    }\n    \n   private:\n    AcaNode *children_[letters];\n    AcaNode *fail_;\n    int depth_;\n  };\n  \n  class AhoCorasickAutomation {\n   public:\n    AhoCorasickAutomation(const vector<string> &words) : root_{} {\n      build(words);\n    }\n    \n    vector<int> get_jump(const string &target) {\n      const int n = static_cast<int>(target.size());\n      vector<int> ret(n);\n      AcaNode *node = &root_;\n      for (int i = 0; i < n; ++i) {\n        AcaNode *next_node = node->get_child(target[i]);\n        while (next_node == nullptr && node != &root_) {\n          node = node->fail();\n          next_node = node->get_child(target[i]);\n        }\n        node = next_node;\n        if (node == nullptr) {\n          node = &root_;\n        } else {\n          ret[i - node->depth() + 1] = node->depth();\n        }\n      }\n      return ret;\n    }\n    \n   private:\n    void build(const vector<string> &words) {\n      for (const string &word : words) {\n        AcaNode *node = &root_;\n        const int n_word = static_cast<int>(word.size());\n        for (int i = 0; i < n_word; ++i) {\n          node = node->get_or_create_child(word[i]);\n          node->set_depth(i + 1);\n        }\n      }\n      \n      queue<AcaNode *> q({&root_});\n      while (!q.empty()) {\n        AcaNode * const node = q.front();\n        q.pop();\n        \n        for (int letter = 0; letter < letters; ++letter) {\n          const char c = a + letter;\n          AcaNode * const child = node->get_child(c);\n          if (child == nullptr) {\n            continue;\n          }\n          \n          AcaNode *parent = node;\n          for (;\n               parent->fail() != nullptr && child->fail() == nullptr;\n               parent = parent->fail()) {\n            AcaNode *target = parent->fail()->get_child(c);\n            if (target != nullptr) {\n              child->set_fail(target);\n            }\n          }\n          if (child->fail() == nullptr) {\n            child->set_fail(&root_);\n          }\n          q.emplace(child);\n        }\n      }\n      \n      root_.set_fail(&root_);\n    }\n    \n    AcaNode root_;\n  };\n  \n public:\n  int minValidStrings(const vector<string> &words, const string &target) {\n    const int n_target = static_cast<int>(target.size());\n    AhoCorasickAutomation aca(words);\n    const vector<int> jump = aca.get_jump(target);\n    int ret = 0;\n    for (int max_reach = 0, next_max_reach = 0, i = 0; i < n_target && max_reach < n_target; ++i) {\n      next_max_reach = max(next_max_reach, i + jump[i]);\n      if (i == max_reach) {\n        if (next_max_reach == max_reach) {\n          ret = -1;\n          break;\n        }\n        ++ret;\n        max_reach = next_max_reach;\n      }\n    }\n    return ret;\n  }\n};\n```
[]