KMP Algo
Intuition\nUse kmp to find the target string from backwards . We will check the longest common prefix from the words that matches with the target from the last 
# Intuition\nUse kmp to find the target string from backwards . We will check the longest common prefix from the words that matches with the target from the last . \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\n5*1e6\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 []\nclass Solution {\npublic:\n    vector<int>find(string ashu)\n    {\n        int n = ashu.size();\n        vector<int>lps(n , 0);\n        int j =0 ;\n        int i =1 ;\n        while(i < n )\n        {\n            if(ashu[i] == ashu[j])\n            {\n                j++;\n                lps[i] = j;\n                i++;\n            }\n            else\n            {\n                if(j!=0)\n                {\n                    j = lps[j-1];\n                }\n                else{\n                    lps[i] = 0;\n                    i++;\n                }\n            }\n        }\n        return lps;\n    }\n    int minValidStrings(vector<string>& words, string target) {\n        int n = words.size();\n        vector<vector<int>>ashu;\n        for(auto i : words)\n        {\n            ashu.push_back(find(i + "#" + target));\n        }\n        int len = target.size();\n        int match =0 ;\n        while(len > 0)\n        {\n            int ans = 0 ;\n            for(int i = 0 ; i < n ; i++)\n            {\n                ans = max(ans , ashu[i][words[i].size() + len]);\n            }\n            if(ans == 0)return -1;\n            match++;\n            len -= ans ;\n        }\n        return match;\n    }\n};\n```
['C++']