Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
这道题给定的words中的单词长度都是一样的，从连续的s子字符串中找出words中的所有单词，并且words中对应的连续的s是不能重叠的，words的顺序可以打乱；
1、从s中找出所有words中存在的单词
2、在长度为words.size()*words[0].length()的s中，是否存在words中所有的单词，并且不重叠；
这里给的关键信息是words中的单词都是一样长的，所以可以通过定长的方式进行匹配；
vector<int> findSubstring(string s, vector<string>& words) { vector<int> result; if (words.size() == 0) return result; else if (words[0].length() == 0) return result; else if (s.length() < words.size()*words[0].length()) return result; map<string, int> word_count; for (auto iter = words.begin(); iter != words.end(); ++iter) { auto index = word_count.find(*iter); if (index != word_count.end()) (index->second)++; else word_count[*iter] = 1; } for (int i = 0; i < words[0].length(); ++i) { map<string, int> s_count; int count = 0; for (int j = i; j < s.length() - words[0].length() + 1; j += words[0].length()) { auto index = word_count.find(s.substr(j, words[0].length())); if (index == word_count.end()) { s_count.clear(); count = 0; continue; } ++count; auto s_index = s_count.find(index->first); if (s_index != s_count.end()) (s_index->second)++; else s_count[index->first] = 1; if (count == words.size() && s_count == word_count) { result.push_back(int(j - words[0].length() * (words.size()-1))); } if (count == words.size()) { s_index = s_count.find(s.substr(j - words[0].length() * (words.size()-1), words[0].length())); (s_index->second)--; if (s_index->second == 0) s_count.erase(s_index); --count; } } } return result; }
如上，先将words装到map里面，能够快速查找；
找到words的总字符长度；然后进行匹配，如果匹配则保存结果，如果不匹配，则把末尾的那个单词去掉，重新继续增加单词进去重新匹配；
leetcode 30. Substring with Concatenation of All Words
原文：https://www.cnblogs.com/czwlinux/p/12343063.html
