Solution using dp + segment tree + binary search
\n\n# Code\ncpp []\nclass Hash{\n    private:\n    const long long mod1=999999929;\n    const long long mod2=999999937;\n    const long long mod3=(long long)(1e
\n\n# Code\n```cpp []\nclass Hash{\n    private:\n    const long long mod1=999999929;\n    const long long mod2=999999937;\n    const long long mod3=(long long)(1e15)+7;\n    \n    const long long p1=1001; // should be greater than the length of the string;\n    const long long p2=1003; // should be greater than the length of the string;\n    \n    const long long p3=99911; // should be greater than the length of the string;\n    \n    public:\n    vector<long long>pref1;\n    vector<long long>pref2;\n    vector<long long>base_pow1;\n    vector<long long>base_pow2;    \n    string s;\n    long long n;\n    \n    Hash(const string &a)\n    {\n        s=a;\n        n=s.length();\n        pref1.assign(n+1,0);\n        pref2.assign(n+1,0);\n        base_pow1.assign(n+1,0);\n        base_pow2.assign(n+1,0);\n        build();\n    }\n    void build()\n    {\n        base_pow1[0]=1;\n        \n        base_pow2[0]=1;\n        pref1[0]=1;\n        pref2[0]=1;\n        \n        for(long long i=1;i<=n;i++)\n        {\n            base_pow1[i]=(base_pow1[i-1]*p1)%mod1;\n            base_pow2[i]=(base_pow2[i-1]*p2)%mod2;\n            \n            pref1[i]=((pref1[i-1]*p1)%mod1+s[i-1]+997)%mod1;\n            \n            pref2[i]=((pref2[i-1]*p2)%mod2+s[i-1]+997)%mod2;\n        }\n        \n    }\n    \n    long long getHash(long long l,long long r)\n    {\n        long long h1=pref1[r+1];\n        \n        h1-=(pref1[l]*base_pow1[r-l+1])%mod1;\n        h1=(h1%mod1+mod1)%mod1;\n        \n        long long h2=pref2[r+1];\n        \n        h2-=(pref2[l]*base_pow2[r-l+1])%mod2;\n        \n        h2=(h2%mod2+mod2)%mod2;\n        \n        long long h3=((h1*p3)%mod3+h2)%mod3;\n        \n        return h3;\n    }\n};\nclass SegmentTree{\n    private:\n    vector<long long>tree;\n    long long n;\n    vector<long long>arr;\n    public:\n    SegmentTree(vector<long long>&a)\n    {\n        arr=a;\n        n=(long long)a.size();\n        tree.assign(4*n+1,0);\n        // cout<<n<<endl;\n        build(0,n-1,0);\n    }\n\n    void build(long long ss,long long se,long long si)\n    {\n        if(ss==se)\n        {\n            tree[si]=arr[se];\n            return;\n        }\n\n        long long mid=(ss+se)/2;\n        build(ss,mid,2*si+1);\n        build(mid+1,se,2*si+2);\n        tree[si]=min(tree[2*si+1],tree[2*si+2]);\n    }\n\n    void update(long long ss,long long se,long long si,long long idx,long long val)\n    {\n        if(ss==se)\n        {\n            tree[si]=val;\n            return;\n        }\n\n        long long mid=(ss+se)/2;\n        if(idx<=mid)\n        {\n            update(ss,mid,2*si+1,idx,val);\n        }\n        else\n        {\n            update(mid+1,se,2*si+2,idx,val);\n        }\n        tree[si]=min(tree[2*si+1],tree[2*si+2]);\n    }\n\n    long long query(long long ss,long long se,long long si,long long l,long long r)\n    {\n        if(ss>=l && se<=r)\n        {\n            return tree[si];\n        }\n\n        if(ss>r || se<l)\n        return (long long)(1e9);\n\n        long long mid=(ss+se)/2;\n\n        return min(query(ss,mid,2*si+1,l,r),query(mid+1,se,2*si+2,l,r));\n    }\n\n    long long make_query(long long l,long long r)\n    {\n        return query(0,n-1,0,l,r);\n    }\n\n    void make_update(long long idx,long long val)\n    {\n         update(0,n-1,0,idx,val);\n    }\n\n};\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        Hash ht(target);\n        long long n=(long long)words.size();\n        set<long long>s;\n        for(long long i=0;i<n;i++)\n        {\n            Hash h(words[i]);\n            long long len=words[i].length();\n            for(long long j=0;j<len;j++)\n            {\n                s.insert(h.getHash(0,j));\n            }\n        }\n\n        long long count=0;\n        long long m=target.length();\n        vector<long long>dp(m+1,(long long)(1e9));\n\n        function<long long(long long)>f=[&](long long i)->long long{\n            long long low=i;\n            long long high=m-1;\n            long long res=-1;\n            while(low<=high)\n            {\n                long long mid=(low+high)/2;\n                if(s.find(ht.getHash(i,mid))!=s.end())\n                {\n                    res=mid;\n                    low=mid+1;\n                }\n                else\n                {\n                    high=mid-1;\n                }\n            }\n            return res;\n        };\n        dp[m]=0;\n        if(s.find(ht.getHash(m-1,m-1))!=s.end())\n        dp[m-1]=1;\n        SegmentTree sgt(dp);\n        for(long long i=m-2;i>=0;i--)\n        {\n            long long j=f(i);\n            if(j==-1)\n            continue;\n            dp[i]=min(dp[i],sgt.make_query(i+1,j+1)+1);\n            sgt.make_update(i,dp[i]);\n        }\n        if(dp[0]==(long long)(1e9))\n        return -1;\n        return dp[0];\n\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Greedy', 'Segment Tree', 'Rolling Hash', 'C++']