StringHash + one extra question
Code is at the end.\n\nQuestion itself is pretty straight forward, either KMP or string hash + binary search to find the maximum common prefix, and do some clas
Code is at the end.\n\nQuestion itself is pretty straight forward, either KMP or string hash + binary search to find the maximum common prefix, and do some classical dp, for a common prefix start at $i$ with length $1..T$ where $T$ is the maximum possible common prefix, do the following operation, let $u \\in 1..T$:\n\n$$\ndp[i + u] \\gets \\min(dp[i+u], dp[i] + 1)\n$$\n\nAnd everything is fine. So we only need to range update $1..T$. There are a million ways to do that. My code uses some priority queue but one can always give up using extra brain and throw a segment tree with lazy prop on it. Complexity is obviously $O(n \\log n)$ for some $n$ which is at most sum of all sizes.\n\n---\n\n**A far more interesting extension of question question is following:**\n\nWhat if the question gives like this:\n\n$$\nwords.size() \\leq 1e5, \\sum_{w \\in words} |w| \\leq 2e5\n$$\n\nEvery other situation are the same.\n\nHow do you get the correct answer in appropriate time?\n\nAnswer: use square root decomp. Let $S = \\sum_{w \\in words} |w| \\leq 2e5$. Split $words$ into set $A, B$. Where:\n\n$$\nA = \\{w : |w| \\leq \\sqrt{S}\\}, B = words \\setminus A\n$$\n\nThen, build a trie on $A$. We know this trie only depths $\\sqrt{S}$ at most. For $B$, string hash or KMP or something. We know $|B| \\leq \\sqrt{S}$ also.\n\nThen we can find $T$ in $O(\\sqrt S)$ time . Overall complexity is $O(n \\sqrt{S} + S)$.\n\n---\n\n\n```\ntypedef long long ll;\n\nconstexpr ll BASE = 31, MOD = 1e9 + 7;\nconstexpr ll BASE1 = 31, MOD1 = 1e9 + 7;\n\nconstexpr ll MAXN = 5e4 + 5;\n\nll ps[MAXN * 2];\n\nbool gened = false;\n\nvoid genps() {\n    if (gened) return;\n    gened = true;\n    ps[0] = 1;\n    for (ll i = 1; i < MAXN * 2; i ++) {\n        ps[i] = ps[i - 1] * BASE % MOD;\n    }\n}\n\nll TMP[MAXN * 4];\nll TMPALLOC;\n\nll *tmpalloc(ll T) {\n    ll *a = TMP + TMPALLOC;\n    TMPALLOC += (T + 1);\n    return a;\n}\n\n\nvoid loadhash(ll *a, string &s) {\n    ll M = s.size();\n    s = " " + s;\n    a[0] = 0;\n    for (ll i = 1; i <= M; i ++) {\n        a[i] = (a[i - 1] * BASE1 + s[i] - \'a\' + 1) % MOD1;\n    }\n}\n\nusing larr = ll*;\n\nlarr hshs[MAXN];\nll szs[MAXN];\nll targhash[MAXN];\n\nll query(ll *a, ll l, ll r) {\n    return (a[r] - a[l - 1] * ps[r - l + 1] % MOD1 + MOD1) % MOD1;\n}\n\nll lensame(ll *a, ll starta, ll enda, ll *b, ll startb, ll endb) {\n    if (query(a, starta, starta) != query(b, startb, startb)) {\n        return 0;\n    }\n    ll lo = 1, hi = min(enda - starta + 1, endb - startb + 1);\n    while (lo < hi) {\n        ll mid = (lo + hi + 1) >> 1;\n        if (query(a, starta, starta + mid - 1) == query(b, startb, startb + mid - 1)) {\n            lo = mid;\n        } else {\n            hi = mid - 1;\n        }\n    }\n    return lo;\n}\n\nll N, M;\nmultiset<ll> mxs;\nll dp[MAXN];\n\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        TMPALLOC = 0;\n        genps();\n        N = target.size(), M = words.size();\n        for (ll i = 0; i < M; i ++) {\n            hshs[i] = tmpalloc(words[i].size());\n            szs[i] = words[i].size();\n            loadhash(hshs[i], words[i]);\n        }\n        loadhash(targhash, target);\n\n        priority_queue<pair<ll, ll>, vector<pair<ll,ll>>, greater<>> pq;\n\n        \n        mxs.clear();\n        // handle zero case\n        {\n            ll zmx = 0;\n            for (ll i = 0; i < M; i ++) {\n                zmx = max(zmx, lensame(hshs[i], 1, szs[i], targhash, 1, N));\n            }\n            if (zmx == 0) {\n                return -1;\n            }\n            dp[0] = 0;\n            pq.push({zmx, 1});\n            mxs.insert(1);\n        }\n\n        for (ll i = 1; i <= N; i ++) {\n            while (!pq.empty() && pq.top().first < i) {\n                auto [j, v] = pq.top();\n                pq.pop();\n                mxs.erase(mxs.find(v));\n            }\n\n            if  (mxs.empty()) {\n                return -1;\n            }\n\n            dp[i] = *mxs.begin();\n\n            {\n                ll zmx = 0;\n                for (ll j = 0; j < M; j ++) {\n                    zmx = max(zmx, lensame(hshs[j], 1, szs[j], targhash, i + 1, N));\n                }\n                if (zmx == 0) {\n                    continue;\n                }\n                pq.push({i + zmx, dp[i] + 1});\n                mxs.insert(dp[i] + 1);\n            }\n        }\n        return dp[N];\n    }\n};\n```
['C++']