KMP + Greedy (interval schedule)
Intuition\nWe need to find the minimum prefix-concatenation. The order or the specific way to achieve this is not required. For each point, we need to determine
# Intuition\nWe need to find the minimum prefix-concatenation. The order or the specific way to achieve this is not required. For each point, we need to determine the maximum distance it can travel according to the prefix rule. We can use the KMP algorithm for each word to calculate this maximum distance. Once we know the distance it can travel, we can convert the problem into an interval scheduling problem, where overlaps are allowed.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: o(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: o(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> dp,cnt;\n    unordered_map<char,vector<int>> map;\n    int m,n;\n    int minValidStrings(vector<string>& w, string t) {\n        m=t.size();\n        n=w.size();\n        dp.resize(m+1,INT_MAX);cnt.resize(m,0);\n        dp[m]=0;\n        for(int i1=0;i1<n;i1++){\n            string s=w[i1];\n            vector<int> a(s.size(),0),b(m,0);\n            kmp_int(s,a);\n            int i=0,j=0;\n            while(i<m){\n                if(t[i]==s[j]){\n                    b[i]=j+1;\n                    int k=i+1-b[i];\n                    cnt[k]=max(cnt[k],b[i]);\n                    j++;\n                    if(j==s.size()) j=a[j-1];\n                    i++;\n                }else if(j!=0) j=a[j-1];\n                else i++;\n            }\n        }\n        int count=0,l=0,r=0;\n        //greedy aproach\n        while(l<m){\n            r=max(r,l+cnt[l]);\n            if(r<=l) return -1;\n            int mx=0;\n            while(l<r){\n                if(l+cnt[l]>r) mx= max(mx,l+cnt[l]);\n                l++;\n            }\n            l=r;\n            r=mx;\n            count++;\n        }\n\n        if(l!=m) return -1;\n        return count;\n    }\n    //kmp is answer\n   void kmp_int(string s,vector<int>&a){\n       int i=1,j=0;\n        while(i<s.size()){\n                if(s.at(i)==s.at(j)){\n                    a[i]=j+1;\n                    j++;\n                    i++;\n                }else if(j!=0) j=a[j-1];\n                else i++;\n        }\n   }\n};\n```
['C++']