leetcode-30 Substring with Concatenation of All Words

題意: 給定一個string s, 另外給定許多同樣長度的words, 求出所有s中的位置,其後的連續序列會包含所有words(中間不能有其他字符)

解題思路: 這題很難, 我的解法效率也不算太高,但還是先貼,我的解法是這樣,先用map求出同樣的word出現幾次,再利用KMP,求出所有word的出現點,之後一個位置一個位置的掃描,即可得解

class Solution {
public:
    int index[100000];
    int pre[100000];
    int check[10000];
    vector<int>ans;
    vector<int> findSubstring(string s, vector<string>& words) {
        memset(check,0,sizeof(check));
        int len=s.size();
        int num=words.size();
        int len1=words[0].size();
        map <string,int> re;
        for(int i=0;i<num;i++)
        {
           
            if(re[words[i]]==0)
                re[words[i]]=i+1;
            check[re[words[i]]]++;
            strStr(s,words[i],re[words[i]]);
            //cout<<re[words[i]]<<" "<<check[re[words[i]]]<<endl;
        }
        len=len-num*len1+1;
        
        for(int i=0;i<len;i++)
        {
            //cout<<index[i]<<endl;
            int arr[10000];
            int count=0;
            memset(arr,0,sizeof(arr));
            for(int j=0;j<num;j++)
            {
                //cout<<index[i+j*len1]<<endl; 
                if((arr[index[i+j*len1]]<check[index[i+j*len1]])&&index[i+j*len1])
                    count++;
                 arr[index[i+j*len1]]++;
            }
            if(count==num)
                ans.push_back(i);
        }
        return ans;
    }
   
    void strStr(string haystack, string needle,int k) {
          int target=haystack.size();
          int target1=needle.size();
          if(target1==0)
              return; 
          int q=-1;
          pre[0]=-1;
          for(int i=1;i<target1;i++)
          {
              while(needle[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(needle[i]==needle[q+1])
                  q++;
              pre[i]=q;
          }
          q=-1;
          for(int i=0;i<target;i++)
          {
              while(haystack[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(haystack[i]==needle[q+1])
              {
                  q++;
                  if(q==target1-1)
                       index[i-target1+1]=k;
              }
          }
    }
};