Z-algorithm +DP + Segment Tree
W=words.length();\nWi=words[i].length();\nT=target.length()\n\n# Complexity\n- Time complexity:O(sum(Wi)+W*T+Tlog(T))\n Add your time complexity here, e.g. O(n)
W=words.length();\nWi=words[i].length();\nT=target.length()\n\n# Complexity\n- Time complexity:O(sum(Wi)+W*T+Tlog(T))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(T + max(Wi))\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass SegmentTree{\n public:  \nvector<int> sgtree;\n\n  \n \n  SegmentTree(int n){\n     sgtree.resize(4*n+1);\n     \n     \n }\n \n \n void build(int index,int low,int high,vector<int> &arr){\n     if(low==high){\n         sgtree[index]=arr[low];\n         return ;\n     }\n     \n     int mid=(low+high)/2;\n     \n     build(2*index+1,low,mid,arr);\n     build(2*index+2,mid+1,high,arr);\n     \n     sgtree[index]=min(sgtree[2*index+1],sgtree[2*index+2]);\n     \n     \n }\n \n int query(int index,int low,int high,int l,int h){\n    if(l>h)\n    return 1e6;\n     if(low>h||l>high)\n     return 1e6;\n     \n    else if(l<=low&&high<=h)\n     return sgtree[index];\n     \n     \n     else{\n         int mid=(low+high)/2;\n         \n         return min(query(2*index+1,low,mid,l,h),query(2*index+2,mid+1,high,l,h));\n     }\n }\n \n void update(int index,int low,int high,int i,int val){\n     if(low==high){\n         sgtree[index]=val;\n         return ;\n     }\n     \n     int mid=(low+high)/2;\n     \n     if(i<=mid)\n     update(2*index+1,low,mid,i,val);\n     \n     else\n     update(2*index+2,mid+1,high,i,val);\n     \n     sgtree[index]=min(sgtree[2*index+1],sgtree[2*index+2]);\n }\n};\nclass Solution {\npublic:\n     vector<int> zfunction(string s){\n        int n=s.size();\n        vector<int> z(n,0);\n\n        int l=0,r=0;\n\n        for(int i=1;i<n;i++){\n            z[i]=max(0,min(z[i-l],r-i+1));\n\n            while(s[z[i]]==s[z[i]+i])\n            z[i]++;\n\n            if(i+z[i]-1>r){\n                l=i;\n                r=i+z[i]-1;\n            }\n        }\n\n        return z;\n     }\n    int minValidStrings(vector<string>& words, string target) {\n        \n       int m=target.size();\n\n       vector<int> v(m,0);\n\n       for(auto &i:words){\n\n        int n=i.size();\n        auto z=zfunction(i+"%"+target);\n\n        for(int j=n+1,k=0;j<z.size();j++,k++){\n           v[k]=max(v[k],z[j]);\n        }\n\n       }\n\n      \n\n        vector<int> dp(m+1,1e6);\n\n        SegmentTree sg(m+1);\n         dp[m]=0;\n        sg.build(0,0,m,dp);\n\n       \n\n        for(int i=m-1;i>=0;i--){\n           int len=v[i];\n\n           int mini=sg.query(0,0,m,i+1,i+len);\n\n           dp[i]=1+mini;\n\n           sg.update(0,0,m,i,dp[i]);\n        }\n\n      \n\n        return (dp[0]>=1e6)?-1:dp[0];\n\n\n    }\n};\n```
['String', 'Dynamic Programming', 'Segment Tree', 'String Matching', 'C++']