题解

---

题目描述

即从字符串s中找出某个子串，此子串是长度一致的子串集合words的某种全排列，返回这些子串的开始位置。如：s:"barfoofoobarthefoobarman",words:["bar","foo","the"];结果为[6,9,12]。

题解

假设原字符串s长度为n，words中元素长度为k，把k个字符当成一个整体来比较，即划分k趟进行遍历，再运用KMP思想进行匹配。时间复杂度约为O(k*n)。

此处注意的是容器的选择，基于二叉树的容器存取并不如基于哈希的容器存取快。以下代码采取了unordered_map作为容器记录前面的匹配情况。

代码

typedef std::string _Type;class Solution {public:    typedef std::unordered_map<_Type, int> UMAP;    std::vector
    
      findSubstring(const std::string& s, std::vector
     
      & words) {        std::vector
      
        vec;        int wsize = words.size(), ssize = s.size();        if (wsize == 0 || ssize == 0)            return vec;        UMAP all;        for (int i = 0; i < wsize; ++i)            ++(all[words[i]]);        for (int mod = 0, len = words[0].size(); mod < len; ++mod) {            UMAP had;            for (int j = mod, start = mod, end = ssize - wsize * len; j <= end; ) {                std::string tmpStr(s.substr(j, len));                j += len;                UMAP::iterator it(all.find(tmpStr));                if (it == all.end()) {                    had.clear();                    start = j;                    end = ssize - wsize * len;                } else {                    if (it->second > had[tmpStr]) {                        ++(had[tmpStr]);                        if (j - start == wsize * len) {                            --(had[s.substr(start, len)]);                            vec.push_back(start);                            start += len;                        } else {                            end += len;                        }                    } else {                        for (int k = start; ; k += len) {                            std::string stmp(s.substr(k, len));                            if (stmp == tmpStr) {                                start = k + len;                                break;                            }                            --(had[stmp]);                            end -= len;                        }                    }                }            }        }        return vec;    }};
      
     
    

总结

主要应用了KMP匹配的思想。