[LeetCode] Substring with Concatenation of All Words(good)

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

For example, given: S: "barfoothefoobarman" L: ["foo", "bar"]

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

方法：分组循环，不要在S中直接遍历，而是把S按照L中每个字符串的长度进行分组，妙

class Solution {
private:
    vector<int> res;
    map<string,int> cntL;
    map<string,int> cn;//存储L中string及其出现次数
    int n ;
public:
    vector<int> findSubstring(string S, vector<string> &L){
        res.clear();
        cntL.clear();
        cn.clear();

        n = S.length();
        int e = L.size();
        int t = L[0].length();
        int k = 0;//k表示L中一共有几个string

        for(int i = 0; i < e ; i++){//在cn中存储L中string及其出现次数
            if(cn.count(L[i]) == 0){
                cn[L[i]] = 1;
                k++;
            }else{
                cn[L[i]] += 1;
                k++;
            }
        }//end for

        string s0 ,s1;
        int r = 0;
        int st = 0;

        for(int j = 0 ; j < t ; j++){//L中每个string的长度是t
            r = 0; st = j;
            cntL.clear();
            for(int i = j; i < n; i += t){
                s0 = S.substr(i,t);
                if( cn.count(s0) == 0 || cn[s0] == 0 ){
                    cntL.clear();
                    r =  0;
                    st = i+t;
                }else if(cntL[s0] < cn[s0]){
                    cntL[s0] += 1;//cntL中记录S中出现L中string及次数
                    r++;//r表示S中遇到的L中string的总共数 r <= k
                }else{//如果S中子字符串比L中某个多了，则开始下标st必然要越过这个多出来的字符，这个多出来的字符即是s0
                    s1 = S.substr(st,t);
                    while(s1 != s0){
                        cntL[s1]--;
                        r--;
                        st += t;
                        s1 = S.substr(st,t);
                    }
                    st += t;
                }
                if(r == k){//利用上个记录，以免多用时间
                    res.push_back(st);
                    s1 = S.substr(st,t);
                    cntL[s1]--;
                    r--;
                    st += t;
                }
            }//end for    
        }//end for
        sort(res.begin(),res.end());
        return res ;    
    }//end func
};