simple cpp
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nstruct SegTree {\npublic:\n \n    SegTree (int _n) : n (_n) {\n        tree.resize(4*n, 1e9);\n    }\n    \n    int query (int x, int y) {\n        return query (x, y, 0, n-1, 0);\n    }\n    \n    void update (int ind, int val) {\n        update (ind, val, 0, n-1, 0);\n    }\n \nprivate:\n    \n    vector<int> tree;\n    int n;\n    \n    int query (int x, int y, int l, int r, int i) {\n        if (r < x || l > y) return 1e9;\n        if (l >= x && r <= y) return tree[i];\n        \n        int m = (l+r) >> 1;\n        return min(\n            query (x, y, l, m, i*2+1),\n            query (x, y, m+1, r, i*2+2)\n        );\n    }\n    \n    void update (int ind, int val, int l, int r, int i) {\n        if (l == r) {\n            tree[i] = val;\n            return;\n        }\n        \n        int m = (l+r) >> 1;\n        if (m >= ind) update (ind, val, l, m, i*2+1);\n        else update (ind, val, m+1, r, i*2+2);\n        \n        tree[i] = min(tree[i*2+1], tree[i*2+2]);\n    }\n};\n\n\nclass Solution {\n    \n    vector<int> z_function(string s) {\n        int n = s.size();\n        vector<int> z(n);\n        int l = 0, r = 0;\n        for(int i = 1; i < n; i++) {\n            if(i < r) {\n                z[i] = min(r - i, z[i - l]);\n            }\n            while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {\n                z[i]++;\n            }\n            if(i + z[i] > r) {\n                l = i;\n                r = i + z[i];\n            }\n        }\n        return z;\n    }\n    \n    vector<int> longest_match;\n\n    void AmmendLongestMatch (const string& word, const string& target) {\n        string s = word + "$" + target;\n        vector<int> z = z_function(s);\n        \n        for (int i = 0; i < target.length(); i ++) {\n            longest_match[i] = max (longest_match[i], z[i+word.length()+1]);\n        }\n    }\n    \npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        longest_match.clear();\n        longest_match.resize(target.length(), 0);\n        \n        for (auto w: words) AmmendLongestMatch (w, target);\n        \n        int n = target.size();\n        SegTree max_len_tree(n+1);\n        max_len_tree.update(n, 0);\n                \n        for (int j = n-1; j >= 0; j --) {\n            int len = longest_match[j];\n            if (len == 0) continue;\n            \n            int max_len = 1 + max_len_tree.query (j+1, j+len);\n            max_len_tree.update (j, max_len);      \n        }\n        \n        int ans = max_len_tree.query(0, 0);\n        if (ans == 1e9) ans = -1;\n        return ans;\n    }\n};\n\n/*\n#define pii pair<int, int>\n#define F first\n#define S second\n\nconst int N = 5e4+1;\nconst int P = 31;\nconst int M = 1e9+7;\n\nconst int INF = 1e9;\n\ntypedef long long int ll;\n\nclass Solution {\n    \n    vector<ll> p_pow;\n    vector<ll> inv_p_pow;\n    \n    // a^b % M\n    ll FastPower (ll a, ll b) {\n        ll ans = 1;\n        while (b) {\n            if (b&1) ans = (ans * a) % M;\n            a = (a*a) % M;\n            b /= 2;\n        }\n        return ans;\n    }\n    \n    void ComputePower() {\n        if (!p_pow.empty()) return;\n        \n        p_pow.resize(N, 1);\n        for (int i = 1; i < N; i ++)\n            p_pow[i] = (p_pow[i-1] * P) % M;\n        \n        inv_p_pow.resize(N, 1);\n        \n        inv_p_pow[N-1] = FastPower (p_pow[N-1], M-2);\n        for (int i = N-2; i > 0; i --)\n            inv_p_pow[i] = (inv_p_pow[i+1] * P) % M;\n    }\n    \n    vector<ll> HashIt (const string& s) {\n        int S = s.size();\n        vector<ll> prefix_hash(S+1, 0);\n\n        for (int i = 1; i <= S; i++) {\n            ll cur = (p_pow[i] * (s[i-1]-\'a\'+1)) % M;\n            prefix_hash[i] = (prefix_hash[i-1] + cur) % M;\n        }\n        return prefix_hash;\n    }\n    \n    inline ll HashOfRange (int l, int r, vector<ll>& prefix_hash) {        \n        ll hash = (prefix_hash[r] - prefix_hash[l-1] + M) % M;\n        return (hash * inv_p_pow[l-1]) % M;\n    }\n    \n    int LongestMatching (int st, vector<ll>& prefix_hash_target, unordered_map<int, int>& hash_and_len) {\n        int l = st, r = prefix_hash_target.size() - 1;\n        \n        while (l < r) {\n            int m = (l+r) >> 1;\n            int hash = HashOfRange (st, m+1, prefix_hash_target);\n            \n            auto it = hash_and_len.find(hash);\n            if (it == hash_and_len.end()) r = m;\n            else l = m+1;\n        }\n        \n        int len = r - st + 1;\n        int hash = HashOfRange (st, l, prefix_hash_target);\n        if (hash_and_len.find(hash) == hash_and_len.end()) len--;\n        return len;\n    }\n    \npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        ComputePower();\n        \n        unordered_map<int, int> hash_and_len;\n        for (auto w : words) {\n            vector<ll> hash = HashIt(w);\n            for (int l = 1; l < hash.size(); l ++) hash_and_len[hash[l]] = l;\n        }\n        \n        int n = target.size();\n        SegTree max_len_tree(n+2);\n        max_len_tree.update(n+1, 0);\n        \n        vector<ll> prefix_hash_target = HashIt(target);\n        \n        for (int j = n; j > 0; j --) {\n            int len = LongestMatching (j, prefix_hash_target, hash_and_len);\n            if (len == 0) continue;\n            \n            int max_len = 1 + max_len_tree.query (j+1, j+len);\n            max_len_tree.update (j, max_len);            \n        }\n        \n        int ans = max_len_tree.query(1, 1);\n        if (ans == 1e9) ans = -1;\n        return ans;\n    }\n};\n*/\n```
['C++']