【leetcode】 Substring with Concatenation of All Words

地址

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

题目

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

思路

因为所有待匹配字符串都是长度相同，每两个可匹配的字串的起始位置的间隔都是m的正整数数倍（m是待匹配字符串的长度）。所以可以分别考虑匹配起始位置是模m为k的情况。
假设匹配起始位置是模k为0的情况。如果知道每个匹配位置的能匹配哪个字符串或不能匹配任意一个，则这题就是求数列中区间是否包含所以待匹配字符串id。用hash处理每个字符串的匹配问题。
ps:思路不知道如何表达，，，还是看我代码吧

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int cnt[10000],ns[10000],n=s.length(),m=words[0].length(),vn=words.size();
        string tmp=words[0];
        map<string,int>hs;
        set<int>st;
        for(int i=0;i<words.size();i++)
        {
            if(hs[words[i]])
                ns[hs[words[i]]]++;
            else
                hs[words[i]]=i+1,ns[i+1]=1;
        }
        for(int i=0;i<m;i++)
        {
            vector<int>num;
            memset(cnt,0,sizeof cnt);
            for(int j=i;j<n&&j+m<=n;j+=m)
            {
                for(int k=0;k<m;k++)
                    tmp[k]=s[j+k];
                if(hs.find(tmp)!=hs.end())
                    num.push_back(hs[tmp]);
                else
                    num.push_back(0);
            }
            for(int p=0,q=0,k=0;p+vn<=num.size();p++)
            {
                while(q<p+vn)
                {
                    if(num[q]&&(cnt[num[q]]<ns[num[q]]))
                        k++,cnt[num[q]]++;
                    else if(num[q])
                        cnt[num[q]]++;
                    q++;
                }
                if(k==vn)
                    st.insert(p*m+i);
                if(num[p]&&cnt[num[p]]<=ns[num[p]])
                    k--,cnt[num[p]]--;
                else if(num[p])
                    cnt[num[p]]--;
            }
        }
        vector<int>ans;
        for(auto it:st)
            ans.push_back(it);
        return ans;
            
    }
};