don't do this... O(nlog^2n)
Cyclic suffix array. I guess this would be faster if the 100 limit wasn\'t there...\n# Code\ncpp []\n#define all(v) begin(v), end(v)\n\ntemplate<class T>\nstruc
- Cyclic suffix array. I guess this would be faster if the 100 limit wasn\'t there...\n# Code\n```cpp []\n#define all(v) begin(v), end(v)\n\ntemplate<class T>\nstruct Tree {\n    static constexpr T def = INT_MAX;\n    T f(T a, T b) { return min(a, b); }\n    vector<T> t; int n;\n    Tree(int n): t(2*n, def), n(n) {}\n    void update(int i, T v) {\n        for (t[i += n] = v; i /= 2;) t[i] = f(t[i*2], t[i*2+1]);\n    }\n    T query(int l, int r) {\n        T al = def, ar = def;\n        for (l += n, r += n; l < r; l /= 2, r /= 2) {\n            if (l&1) al = f(al, t[l++]);\n            if (r&1) ar = f(t[--r], ar);\n        }\n        return f(al, ar);\n    }\n};\n\nstruct SuffixArray {  // TODO: UPDATE TO USE willy108 VERS https://pastebin.com/JEAuS8a2\n    string str; int n;\n    vector<int> sa, isa;\n    Tree<int> lcp;\n    SuffixArray(string str_): str(str_+\'$\'), n(str.size()), sa(n), isa(n), lcp(n-1) {\n        // sa has size sz(S)+1, starts with sz(S)\n        iota(all(sa), 0);\n        sort(all(sa), [&](int i, int j) { return str[i] < str[j]; });\n        for (int i = 1; i < n; ++i) {\n            int l = sa[i-1], r = sa[i];\n            isa[r] = i > 1 && str[l] == str[r] ? isa[l] : i;\n        }\n        for (int k = 1; k < n; k *= 2) {\n            // currently sorted by first k chars\n            vector<int> s(sa), is(isa), pos(n);\n            iota(all(pos), 0);\n            for (int t: s) {\n                int T = t-k;  // verify that nothing goes out of bounds\n                if (T >= 0) sa[pos[isa[T]]++] = T;\n            }\n            for (int i = 1; i < n; ++i) {\n                int l = sa[i-1], r = sa[i];\n                isa[r] = is[l] == is[r] && is[l+k] == is[r+k] ? isa[l] : i;\n            }\n        }\n        int k = 0;  // Kasai\'s Algo\n        for (int r = 0; r < n-1; ++r) {\n            int l = sa[isa[r]-1];\n            while (l+k < n-1 && str[l+k] == str[r+k]) ++k;\n            lcp.update(isa[r]-1, k);\n            if (k) k--;\n        }\n\t\t// if we cut off first chars of two strings\n\t\t// with lcp k then remaining portions still have lcp k-1\n    }\n    int getLCP(int i, int j) {\n        if (i == j) return n-1-i;\n        int l = isa[i], r = isa[j];\n        if (l > r) swap(l, r);\n        return lcp.query(l, r);\n    }\n};\n\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string s) {\n        int INF = 1000000;\n        string big;\n        vector<int> pos;\n        for (auto& w: words) {\n            pos.push_back(big.size());\n            big += w;\n        }\n        int start = big.size();\n        big += s;\n        SuffixArray sa(big);\n\n        int m = words.size();\n        int n = s.size();\n        vector<int> idx;\n        for (int i = 0; i < m; ++i) idx.push_back(i);\n        sort(idx.begin(), idx.end(), [&](int i, int j) {\n            int lcp = sa.getLCP(pos[i], pos[j]);\n            int sz = min<int>(words[i].size(), words[j].size());\n            if (lcp >= sz) return words[i].size() < words[j].size();\n            return words[i][lcp] < words[j][lcp];\n        });\n\n        // for (int i = 0; i < m; ++i) {\n        //     cout << "> " << words[idx[i]] << endl;\n        // }\n\n        Tree<int> dp(n+2);\n        for (int i = 0; i < n+2; ++i) dp.update(i, INF);\n        dp.update(n, 0);\n        for (int i = n-1; i >= 0; --i) {\n            \n            int l = 0, r = m-1;\n            while (l < r) {\n                int h = (l+r)/2;\n                int lcp = sa.getLCP(pos[idx[h]], start+i);\n                int sz = min<int>(words[idx[h]].size(), n-i);\n                if (lcp >= sz || words[idx[h]][lcp] < s[i+lcp]) l = h+1;\n                else r = h;\n            }\n            // cout << "searching for: " << s.substr(i) << " and found l=" << l << endl;\n            // for (int h = 0; h < m; ++h) {\n            //     int lcp = sa.getLCP(pos[idx[h]], start+i);\n            //     int sz = min<int>(words[idx[h]].size(), n-i);\n            //     cout << ((lcp >= sz || words[idx[h]][lcp] < s[i+lcp]) ? "YES" : "NO" )<< " lcp=" << lcp << " sz=" << sz << endl;\n            // }\n            \n            int lcp = min(sa.getLCP(pos[idx[l]], start+i), min<int>(words[idx[l]].size(), n-i));\n            if (l) {\n                l--;\n                lcp = max(lcp, min(sa.getLCP(pos[idx[l]], start+i), min<int>(words[idx[l]].size(), n-i)));\n\n            }\n\n            dp.update(i, dp.query(i, i+lcp+1) + 1);\n        }\n        int res = dp.query(0, 1);\n        // cout << "RES" << endl;\n        // for (int i = 0; i <= n; ++i) {\n        //     cout << dp.query(i, i+1) << \' \';\n        // }\n        // cout << endl;\n        return res < INF ? res : -1;\n    }\n};\n```
['C++']