编程之美-最短摘要的生成 - 代码物语-Let code talk - ITeye技术网站

编程之美-最短摘要的生成 - 代码物语-Let code talk - ITeye技术网站
包含所有关键字（关键字不要求按用户输入的顺序排列）的长度最短的摘要.
在一个字符串中，找一些目标字符串集合，找到包含所有目标字符串的最小连续子串.
http://chuanwang66.iteye.com/blog/1836718

1. void findMinAbstract(char* w, int wLen, char* q, int qLen){  
2.      //[begin, end]双指针   
3.      int begin=0;  
4.      int end=-1;  
5.        
6.      //最短摘要   
7.      int minLen=wLen+1;   //最短摘要长度   
8.      int minBegin;        //最短摘要开始   
9.      int minEnd;          //最短摘要结束   
10.        
11.      hash_map<char, bool> qHashMap;   //需要找的关键字  
12.      for(int i=0;i<qLen;i++){  
13.          qHashMap[q[i]]=true;  
14.      }  
15.         
16.      hash_map<char, int> qFoundCnt;  //统计找到关键字的次数   
17.      int qFoundNum=0;    //已经找到的关键字个数   
18.        
19.      while(true){  
20.          //在当前状态[begin, end]: 还没找到所有关键字 ，后指针后移   
21.          while(qFoundNum<qLen && end<=wLen-1){  
22.              end++;  
23.                
24.              if(qHashMap[w[end]]==true){//找到关键字   
25.                  if(qFoundCnt[w[end]]==0){//以前找到过   
26.                      qFoundCnt[w[end]]=1;  
27.                      qFoundNum++;  
28.                  }else{ //以前未找到过   
29.                      qFoundCnt[w[end]]++;  
30.                  }  
31.              }  
32.          }  
33.          //在当前状态[begin, end]: 已经找到所有关键字，前指针后移   
34.          while(qFoundNum==qLen && begin<=end){  
35.              if(end-begin+1<minLen){  
36.                  minLen=end-begin+1;  
37.                  minBegin=begin;  
38.                  minEnd=end;  
39.              }  
40.                                   
41.              //前指针后移：去掉 w[begin]   
42.              if(qHashMap[w[begin]]==true){  
43.                  if(qFoundCnt[w[begin]]>1){  
44.                      qFoundCnt[w[begin]]--;  
45.                  }else if(qFoundCnt[w[begin]]==1){  
46.                      qFoundCnt[w[begin]]=0;  
47.                      qFoundNum--;  
48.                  }  
49.              }  
50.                
51.              begin++;  
52.          }  
53.            
54.          if(end>=wLen)  
55.              break;  
56.      }  
57.        
58.        
59.      //显示最短摘要   
60.      for(int i=0;i<wLen;i++){  
61.          cout<<w[i];  
62.      }cout<<endl;  
63.      for(int i=0;i<wLen;i++){  
64.          if(i==minBegin){  
65.              cout<<"b";  
66.          }else if(i==minEnd){  
67.              cout<<"e";  
68.          }else{  
69.              cout<<" ";   
70.          }  
71.      }cout<<endl;  
72.      cout<<"minLen = "<<minLen<<endl;  
73.        
74. }  

http://taop.marchtea.com/07.02.html
http://blog.csdn.net/v_july_v/article/details/6890054
Read full article from 编程之美-最短摘要的生成 - 代码物语-Let code talk - ITeye技术网站