Z - function + segment Tree
Approach\nZ -Function and Segment Tree\n\n# Code\ncpp []\nusing ll = long long;\nvector<int> z_function(string s) {\n    int n = s.size();\n    vector<int> z(n)
# Approach\nZ -Function and Segment Tree\n\n# Code\n```cpp []\nusing ll = long long;\nvector<int> z_function(string s) {\n    int n = s.size();\n    vector<int> z(n);\n    int l = 0, r = 0;\n    for(int i = 1; i < n; i++) {\n        if(i < r) {\n            z[i] = min(r - i, z[i - l]);\n        }\n        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {\n            z[i]++;\n        }\n        if(i + z[i] > r) {\n            l = i;\n            r = i + z[i];\n        }\n    }\n    return z;\n}\nconst int MX =2e5+1;\narray<int,4*MX> t;\nvoid update(int v,int tl,int tr,int pos,int val){\n    if(tl==tr) {\n        t[v] = min(t[v],val);\n        return;\n    }\n    int tm = (tl+tr)>>1;\n    if(pos<=tm) update(v<<1,tl,tm,pos,val);\n    else update(v<<1|1,tm+1,tr,pos,val);\n    t[v] = min(t[v<<1],t[v<<1|1]);\n}\nint query(int v,int tl,int tr,int l,int r){\n    if(l>r) return 1e9;\n    if(r<tl or tr<l){\n        return 1e9;\n    }\n    if(l<=tl and tr<=r){\n        return t[v];\n    }\n    int tm = (tl+tr)>>1;\n    return min(query(v<<1,tl,tm,l,r),query(v<<1|1,tm+1,tr,l,r));\n}\nvoid build(){\n    for(int i=0;i<4*MX;i++) t[i] =1e9;\n}\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        int n = target.size();\n        vector<int> match(n);\n        for(auto g:words){\n            auto res = z_function(g+"#"+target);\n            vector<int> clean(res.begin()+g.size()+1,res.end());\n            for(int i=0;i<n;i++){\n                match[i]=max(match[i],clean[i]);\n            }\n        }\n        build();\n        update(1,0,n,n,0);\n        for(int i=n-1;i>=0;i--){\n            int m = match[i];\n            int q = query(1,0,n,i+1,i+match[i]);\n            update(1,0,n,i,q+1);\n        }\n        int res = query(1,0,n,0,0);\n        return res == 1e9 ? -1 : res;\n    }\n};\n```
['C++']