我们试着降低此问题的复杂度。因为上述思路一再进行查找的时候，总是重复地循环，效率不高。那么怎么简化呢？先来看看这些序列：
w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1
问题在于，如何一次把所有的关键词都扫描到，并且不遗漏。扫描肯定是无法避免的，但是如何把两次扫描的结果联系起来呢？这是一个值得考虑的问题。
沿用前面的扫描方法，再来看看。第一次扫描的时候，假设需要包含所有的关键词，从第一个位置w0处将扫描到w6处：
w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1
那么，下次扫描应该怎么办呢？先把第一个被扫描的位置挪到q0处。
w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1
然后把第一个被扫描的位置继续往后面移动一格，这样包含的序列中将减少了关键词q0。那么，我们便可以把第二个扫描位置往后移，这样就可以找到下一个包含所有关键词的序列。即从w4扫描到w9处，便包含了q1，q0：
w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1
这样，问题就和第一次扫描时碰到的情况一样了。依次扫描下去，在w中找出所有包含q的序列，并且找出其中的最小值，就可得到最终的结果。编程之美上给出了如下参考代码：
//July、updated，2011.10.21。
- int nTargetLen = N + 1; // 设置目标长度为总长度+1
- int pBegin = 0; // 初始指针
- int pEnd = 0; // 结束指针
- int nLen = N; // 目标数组的长度为N
- int nAbstractBegin = 0; // 目标摘要的起始地址
- int nAbstractEnd = 0; // 目标摘要的结束地址
- while(true)
- {
- // 假设未包含所有的关键词，并且后面的指针没有越界，往后移动指针
- while(!isAllExisted() && pEnd < nLen)
- {
- pEnd++;
- }
- // 假设找到一段包含所有关键词信息的字符串
- while(isAllExisted())
- {
- if(pEnd – pBegin < nTargetLen)
- {
- nTargetLen = pEnd – pBegin;
- nAbstractBegin = pBegin;
- nAbstractEnd = pEnd – 1;
- }
- pBegin++;
- }
- if(pEnd >= N)
- Break;
- }
小结：上述思路二相比于思路一，很明显提高了不小效率。我们在匹配的过程中利用了可以省去其中某些死板的步骤，这让我想到了KMP算法的匹配过程。同样是经过观察，比较，最后总结归纳出的高效算法。我想，一定还有更好的办法，只是我们目前还没有看到，想到，待我们去发现，创造。
转载：http://blog.csdn.net/v_july_v/article/details/6890054
