双指针策略（《编程之美》3.5 最短摘要生成）
????? 本文源自《编程之美》3.5 最短摘要生成一课。
?
题意：在一个字符串中，找一些目标字符串集合，找到包含所有目标字符串的最小连续子串。题目虽然叫做“最短摘要生成”，但和实际上的搜索snippet的计算还有较大差距。
?
解法：采用了“双指针”策略，其思想在很多算法设计中都有价值。思想是：开始两个指针都指向缓冲区头部，尾指针向后扫描，直到头指针和尾指针中间包含了全部的关键字；那么头指针向后移动，直到包含全部关键字的这个条件失败。这是截取字符串并和已取得的最小字符串比较，如果小则替换。
?
下面是我的代码
#include <iostream>#include <hash_map.h> //因为hash_map暂不为cpp标准，所以没法<hash_map> using namespace std;void findMinAbstract(char* w, int wLen, char* q, int qLen){ //[begin, end]双指针 int begin=0; int end=-1; //最短摘要 int minLen=wLen+1; //最短摘要长度 int minBegin; //最短摘要开始 int minEnd; //最短摘要结束 hash_map<char, bool> qHashMap; //需要找的关键字 for(int i=0;i<qLen;i++){ qHashMap[q[i]]=true; } hash_map<char, int> qFoundCnt; //统计找到关键字的次数 int qFoundNum=0; //已经找到的关键字个数 while(true){ //在当前状态[begin, end]: 还没找到所有关键字 ，后指针后移 while(qFoundNum<qLen && end<=wLen-1){ end++; if(qHashMap[w[end]]==true){//找到关键字 if(qFoundCnt[w[end]]==0){//以前找到过 qFoundCnt[w[end]]=1; qFoundNum++; }else{ //以前未找到过 qFoundCnt[w[end]]++; } } } //在当前状态[begin, end]: 已经找到所有关键字，前指针后移 while(qFoundNum==qLen && begin<=end){ if(end-begin+1<minLen){ minLen=end-begin+1; minBegin=begin; minEnd=end; } //前指针后移：去掉 w[begin] if(qHashMap[w[begin]]==true){ if(qFoundCnt[w[begin]]>1){ qFoundCnt[w[begin]]--; }else if(qFoundCnt[w[begin]]==1){ qFoundCnt[w[begin]]=0; qFoundNum--; } } begin++; } if(end>=wLen) break; } //显示最短摘要 for(int i=0;i<wLen;i++){ cout<<w[i]; }cout<<endl; for(int i=0;i<wLen;i++){ if(i==minBegin){ cout<<"b"; }else if(i==minEnd){ cout<<"e"; }else{ cout<<" "; } }cout<<endl; cout<<"minLen = "<<minLen<<endl; }int main(){ char* w="abbbbbcaaadebmmmmdcfg"; int wLen=21; char* q="bd"; int qLen=2; findMinAbstract(w, wLen, q, qLen); system("pause"); return 0;}效果： 
?
?