Z function optimization
Intuition\nJust an string optimization problem\n Describe your first thoughts on how to solve this problem. \n\n # Approach \n Describe your approach to solving
# Intuition\nJust an string optimization problem\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n<!-- # Approach -->\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(sumOfWords + target*countWords)= O(10^5+5$*$10^6)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(target+length of word)=O(10^5)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {//3:46am\npublic:\nvector<int> zfn(string s){\n// cout<<s<<endl;\nint n=s.size();\nvector<int>z(n,0);\n    z[0]=s.size();\n    \n    int l=0,r=0;\n    int i=1;\n    while(i<n){\n        if(r>=i){\n            z[i]=min(r-i+1,z[i-l]);\n        }\n        while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) z[i]++;\n\n        if(i+z[i]-1>r) {\n            l=i;\n            r=i+z[i]-1;\n        }\n        i++;\n    }\n    return z;\n}\nint fn(vector<int>v){\n    int n=v.size();\n    int ans=0; int i=0;\n    int last=0,nextLast=0;\n    if(v[0]==0)return -1;\n    while(last<=n-1){\n\n        while(i<=last){\n            nextLast=max(nextLast,i+v[i]);i++;\n        }\n        if(nextLast==last)return -1;\n        ans++;\n        \n        last=nextLast;\n        nextLast=0;\n    }\n    // if(last==n-1)ans++;\n    return ans;\n}\n\n\n    int minValidStrings(vector<string>& words, string target) {\n        int n=target.size();\n        vector<int>pre(n,0);\n        for(auto w:words){\n            string s=w+"#"+target;\n            vector<int>z=zfn(s);\n            \n            for(int i=w.size()+1;i<z.size();i++){\n               \n                pre[i-w.size()-1]=max(pre[i-w.size()-1],z[i]);\n            }\n          \n        }\n        // for(auto it:pre)cout<<it<<" ";cout<<endl;\n        return fn(pre);\n    }\n};\n```
['String', 'Rolling Hash', 'C++']