本文源自《编程之美》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; }
效果:
相关推荐
[指针的编程艺术(第二版)]_蔡明志著_人民邮电出版社_2013.01 完整清晰扫描版,已添加完美书签, 本资源总体积197M,超过上传体积限制,所以分成两卷压缩,此为此一卷,第二卷请找我的其他上传,每个包设置售价2...
《指针的编程艺术》书中全部代码,非常完整,可以很好的帮助你学习
[指针的编程艺术(第二版)]_蔡明志著_人民邮电出版社_2013.01 完整清晰扫描版,已添加完美书签, 本资源总体积197M,超过上传体积限制,所以分成两卷压缩,此为此二卷,第一卷请找我的其他上传,每个包设置售价2...
VC_实时获取鼠标指针坐标编程方法 VC_实时获取鼠标指针坐标编程方法 VC_实时获取鼠标指针坐标编程方法
西门子PLC指针编程
主讲指针在函数和数组中的应用,以及指向指针的指针的进阶。
深入理解双指针 对于C语言的参数传递都是值传递,当传传递一个指针给函数的时,其实质 上还是值传递,除非使用双指针。 在讲双指针之前,还是先讲讲关于C语言函数调用的本质。
本代码为通过highcharts制作的双盘双指针仪表盘; 本代码为通过highcharts制作的双盘双指针仪表盘;
c语言编程题之双指针有序数组的平方
C++双指针的展示,想进阶C++的可以看一下,如果看懂了对指针的理解会有一个新的高度
西门子300指针编程详解. step7 编程之地址概念详解
在编程和算法竞赛中,双指针算法是一种高效的问题解决方法。本资料通过一系列经典问题,如数组操作、链表处理、树和图等数据结构的问题,展示了双指针算法的实际应用场景。通过学习本资料,读者可以快速掌握双指针...
本设计以VC++6.0作为程序开发环境,C语言作为程序开发语言,详细介绍了最短路径的求解算法及其...请用C/C++语言的结构体、指针、数据结构等基础知识,编写程序实现图的结构定义、图的存储,以及求解单源点最短路径。
可以用但指针实现交换,双指针也是可以实现交换的,只要搞懂他们在内存中是怎么存储的
C语言数组 C语言数组指针与编程技巧 C语言数组指针
有关西门子PLC的S7-300中的STEP7指针编程
编程资源—322个精美鼠标指针cur.zip
利用scratch编程,实现指针时钟,包含时针、分针、秒针,模拟现实时钟,指针按时转动,时针、分针、秒针为个角色、内含所有源码和角色、背景
c语言指针编程练习题.pdf