String Hash+Binary Search+BST(std::Map)
Complexity\n\n- n=target.length,m=sum(words.length)\n\n- Time complexity: O(m+n \log(n))\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(m)
# Complexity\n\n- $$n=target.length,m=sum(words.length)$$\n\n- Time complexity: $$O(m+n \\log(n))$$\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 []\n\n\nclass Solution {\npublic:\n    typedef long long ll;\n    vector<unordered_set<ll>> mp[2];\n    ll max_l=0;\n    ll base = 131;\n    ll mod[2]={998244353,1000000007};\n    vector<ll> hast[2];\n    vector<ll> pow[2];\n\n    void get_hash(string s,int id) {\n        ll ans=0;\n        for(int i=0;i<s.size();i++){\n            ans=(ans*base+(ll)s[i])%mod[id];\n            mp[id][i+1].insert(ans);\n        }\n    }\n    void get_hash(string s){\n        get_hash(s,0);get_hash(s,1);\n    }\n\n    void build_hast(string s,int id){\n        hast[id][0]=0;\n        for(ll i=0;i<s.size();i++){\n            hast[id][i+1]=(hast[id][i]*base+s[i])%mod[id];\n        }\n    }\n    void build_hast(string s){\n        build_hast(s,0);build_hast(s,1);\n    }\n\n    ll get_hast(int l,int r,int id){\n        return ((hast[id][r+1]-hast[id][l]*pow[id][r-l+1])%mod[id]+mod[id])%mod[id];\n    }\n\n    bool check(int st,int m){\n        if(m==0) return true;\n        return mp[0][m].count(get_hast(st,st+m-1,0))&&\n        mp[1][m].count(get_hast(st,st+m-1,1));\n    }\n\n    int calc(int st,int l,int r){\n        int m=(l+r)/2;\n        if(l+1>=r){\n            if(check(st,r)){\n                return r;\n            }\n            else{\n                return r-1;\n            }\n        }\n        if(check(st,m)) return calc(st,m,r);\n        else return calc(st,l,m-1);\n    }\n    vector<int> vec[50005];\n    int minValidStrings(vector<string>& words, string t) {\n        max_l=t.size();\n        for(int i=0;i<words.size();i++){\n            max_l=max((ll)words[i].size(),max_l);\n        }\n        for(int i=0;i<2;i++){\n            mp[i].resize(max_l+10);\n            hast[i].resize(max_l+10);\n            pow[i].resize(max_l+10);\n        }\n        for(int i=0;i<2;i++){\n            pow[i][0]=1;\n            for(int j=1;j<=max_l;j++){\n                pow[i][j]=pow[i][j-1]*base%mod[i];\n            }\n        }\n        for(int i=0;i<words.size();i++){\n            get_hash(words[i]);\n        }\n        int n=t.size();\n        build_hast(t);\n\n        vector<int> dp(n+1,1000000000);\n        dp[0]=0;\n        map<int,int> mp1;\n\n        for(int i=0;i<n;i++){\n            pair<int,int> pp;\n            pp.first=dp[i]+1,pp.second=calc(i,0,n-i);            \n            if(pp.second==0&&mp1.size()==0) return -1;\n            if(pp.second!=0){\n                pp.second=i+pp.second;\n                vec[pp.second].push_back(pp.first);\n                mp1[pp.first]++;\n            }\n            dp[i+1]=mp1.begin()->first;\n            for(int j=0;j<vec[i+1].size();j++){\n                mp1[vec[i+1][j]]--;\n                if(mp1[vec[i+1][j]]==0) mp1.erase(vec[i+1][j]);\n            }\n        }\n        return dp[n];\n    }\n};\n```
['C++']