KMP
Intuition: if we match right-to-left, we can greedily take the largest prefix in words that is also a suffix in target.\n> It can be proven by a contradiction. 
**Intuition:** if we match right-to-left, we can greedily take the largest prefix in `words` that is also a suffix in `target`.\n> It can be proven by a contradiction. As a quick example, say we matched two prefixes ["abc]["def"].\n> - If there is a longer second prefix, e.g. ["ab]["cdef"], picking it will never make the result worse.\n> - However, if we use a shorter second prefix, e.g. ["abc]?["ef"], the result *could* become worse.\n\n\nNow, the trick is how to find the largest prefix/suffix efficiently.\n\nFor that, we employ the KMP algorithm. The prefix function for `words[i] + "#" + target` returns the prefix array.\n\nThe corresponding element of that array shows the longest suffix that is also a prefix.\n\n> We track the maximum prefix/suffix size for each position in `target` using the `ps` array. \n\nThe `prefix_function` method is taken as-is from the CP-A web site.\n\n**Complexity Analysis**\n- Time: O(n + k * m), where n is len(words), m is len(target) and k is the number of words.\n- Memory: O(n + k * m)\n\n**C++**\n```cpp \nvector<int> prefix_function(const string &s) {\n    int n = (int)s.length();\n    vector<int> pi(n);\n    for (int i = 1; i < n; i++) {\n        int j = pi[i-1];\n        while (j > 0 && s[i] != s[j])\n            j = pi[j-1];\n        if (s[i] == s[j])\n            j++;\n        pi[i] = j;\n    }\n    return pi;\n}    \nint minValidStrings(vector<string>& words, string target) {\n    vector<int> ps(target.size() + 1);\n    for (const auto &w : words) {\n        auto pi = prefix_function(w + "#" + target);\n        for (int i = 1; i <= target.size(); ++i)\n            ps[i] = max(ps[i], pi[w.size() + i]);\n    }\n    int len = target.size(), res = 0;\n    for (; len && ps[len]; ++res)\n        len -= ps[len];\n    return len == 0 ? res : -1;\n}\n```
['C']