双指针策略（《编程之美》3.5 最短摘要生成）

      本文源自《编程之美》3.5 最短摘要生成一课。

 

题意：在一个字符串中，找一些目标字符串集合，找到包含所有目标字符串的最小连续子串。题目虽然叫做“最短摘要生成”，但和实际上的搜索snippet的计算还有较大差距。

 

解法：采用了“双指针”策略，其思想在很多算法设计中都有价值。思想是：开始两个指针都指向缓冲区头部，尾指针向后扫描，直到头指针和尾指针中间包含了全部的关键字；那么头指针向后移动，直到包含全部关键字的这个条件失败。这是截取字符串并和已取得的最小字符串比较，如果小则替换。

 

下面是我的代码

#include <iostream>

#if 0
#include <hash_map.h>  //因为hash_map暂不为cpp标准，所以没法<hash_map> 
#else
#include <tr1/unordered_map>
#define hash_map std::tr1::unordered_map
#endif

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);    

    return 0;
}

效果：