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).
这里使用一种巧妙点的暴力法和一种原始的暴力法来解决这个问题。巧妙点的暴力法是参考了LeetCode上的，然后改进来的，时间上快了差不多一倍，有图有真相：
LeeCode上的代码都是200多ms，我下面的代码是100多ms。最后一个1632ms的是原始的暴力法。
主要思想是一样的，最主要的就是会如何分段例如：
三个字母一段 abc def ghi jk那么可以在分a bcd efg hij k还可以分ab cde fgh ijk然后再分就重复了。
所以三个字母分为一段的只有三种分法，同样道理四个字母的只有四种分法。
懂得这个思想就能写出比原始的暴力法快出10倍多的程序了。
我的代码改进的地方主要是：
当检测到有一个单词不相等的时候，如果后面的主串的字母数剩下小于lLen*len（L中的单词数和每个单词的字母数的乘积），那么就不用继续比较了。
LeetCode上的还把map换成了vector，以方便查找，不过感觉也没有这个必要。
下面是我的程序：
[cpp]
vector findSubstring(string S, vector &L)
{
int sLen = S.length();
int lLen = L.size();
if (lLen < 1) return vector();
int len = L[0].length();
vector res;
map LMap;
map countMap;
string index;
for (auto x: L)
LMap[x]++;
//熟记这个思维，巧妙地分段
for (int d = 0; d < len; d++)
{
//注意：是i=d不是i=0;
for (int i = d; i <= sLen-lLen*len; i += len)
{
int start = i;
index = S.substr(i,len);
//注意：后面的是i<=sLen-len不是sLen-lLen*len
while (LMap.count(index) > 0 && i <= sLen-len)
{
countMap[index]++;
//这里就不能用map的count函数了，因为count只会返回0或1
//一定要熟悉STL函数的各种用法，否则会出错。
//这个函数把握不好，结果浪费大量的时间。
//本题卡的最长时间的是这个小小的函数和程序结构开始没写好
if (countMap[index] > LMap[index])
{
string sTemp = S.substr(start,len);
while (sTemp != index)
{
start += len;
sTemp = S.substr(start,len);
//每前进一步，减少一个相等元素
countMap[sTemp]--;
}
countMap[index]--;
start += len;
}
i+=len;
if ((i-start)/len == lLen)
{
res.push_back(start);
string sTemp = S.substr(start, len);
countMap[sTemp]--;
start+=len;
}
index = S.substr(i,len);
}
countMap.clear();
}
}
return res;
}
下面是LeetCode上的不错的程序：
http://discuss.leetcode.com/questions/210/substring-with-concatenation-of-all-words
[cpp]
class Solution {
public:
vector findSubstring(string S, vector &L) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m = S.size(), n = L.size(), len = L[0].size();
map ids;
vector need(n, 0);
for (int i = 0; i < n; ++i) {
if (!ids.count(L[i])) ids[L[i]] = i;
need[ids[L[i]]]++;
}
vector s(m, -1);
for (int i = 0; i < m - len + 1; ++i) {
string key = S.substr(i, len);
s[i] = ids.count(key) ids[key] : -1;
}
vector ret;
for (int offset = 0; offset < len; ++offset) {
vector found(n, 0);
int count = 0, begin = offset;
for (int i = off