传统的简单匹配算法O(m*n):
int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符 起存在和串 T 相同的子串,则称匹配成功,返回第一个 这样的子串在串 S 中的下标,否则返回 -1 */ int i = pos, j = 0; while ( S[i+j] != '/0'&& T[j] != '/0') if ( S[i+j] == T[j] ) j ++; // 继续比较后一字符 else { i ++; j = 0; // 重新开始新的一轮匹配 } if ( T[j] == '/0') return i; // 匹配成功 返回下标 else return -1; // 串S中(第pos个字符起)不存在和串T相同的子串 } // Index_BF
KMP算法O(m+n)
1、首先求出模式串的模式值next[i](当匹配失效出现时,失效字符前面的next[i]个字符与模式串的开头next[i]个字符串一样,下次比较的时候直接跳过前next[i]个字符)
模式值函数的定义:
(1)next[0]= -1 意义:任何串的第一个字符的模式值规定为-1。
(2)next[j]= -1 意义:模式串T中下标为j的字符,如果与首字符
相同,且j的前面的j—k个字符与开头的j—k
个字符不等(或者相等但T[k]==T[j])(1≤k<j)。
如:T=”abCabCad” 则 next[6]=-1,因T[3]=T[6]
(3)next[j]=k 意义:模式串T中下标为j的字符,如果j的前面k个
字符与开头的k个字符相等,且T[j] != T[k] (1≤k<j)。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].(1≤k<j);
(4) next[j]=0 意义:除(1)(2)(3)的其他情况
源程序如下: void get_nextval(const char *T, int next[]) { // 求模式串T的next函数值并存入数组 next。 int j = 0, k = -1; next[0] = -1; while ( T[j/*+1*/] != '/0' ) { if (k == -1 || T[j] == T[k]) { ++j; ++k; if (T[j]!=T[k]) next[j] = k; else next[j] = next[k]; }// if else k = next[k]; }// while ////这里是我加的显示部分 // for(int i=0;i<j;i++) //{ // cout<<next[i]; //} //cout<<endl; }// get_nextval 另一种写法,也差不多。 void getNext(const char* pattern,int next[]) { next[0]= -1; int k=-1,j=0; while(pattern[j] != '/0') { if(k!= -1 && pattern[k]!= pattern[j] ) k=next[k]; ++j;++k; if(pattern[k]== pattern[j]) next[j]=next[k]; else next[j]=k; } ////这里是我加的显示部分 // for(int i=0;i<j;i++) //{ // cout<<next[i]; //} //cout<<endl; }
2、KMP匹配 #include <iostream.h> #include <string.h> int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。 { if( !Text||!Pattern|| Pattern[0]=='/0' || Text[0]=='/0' )// return -1;//空指针或空串,返回-1。 int len=0; const char * c=Pattern; while(*c++!='/0')//移动指针比移动下标快。 { ++len;//字符串长度。 } int *next=new int[len+1]; get_nextval(Pattern,next);//求Pattern的next函数值 int index=0,i=0,j=0; while(Text[i]!='/0' && Pattern[j]!='/0' ) { if(Text[i]== Pattern[j]) { ++i;// 继续比较后继字符 ++j; } else { index += j-next[j]; if(next[j]!=-1) j=next[j];// 模式串向右移动 else { j=0; ++i; } } }//while delete []next; if(Pattern[j]=='/0') return index;// 匹配成功 else return -1; } int main()//abCabCad { char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc"; char*pattern="adCadCad"; //getNext(pattern,n); //get_nextval(pattern,n); cout<<KMP(text,pattern)<<endl; return 0; }
详细分析参考: http://blog.chinaunix.net/uid-27164517-id-3280128.html
相关推荐
今天遇到一个KMP算法的题,以前根本没见过,上网查了好多关于KMP,但是讲的都不是很清楚,看的一头雾水,然后就自己研究做出了一个小程序,附上了相关算法解释!希望这个小程序可以帮助大家很好的了解KMP算法Next及...
Aho-Corasick 算法, 用于从文本串中识别一组关键字,所需的时间和文本长度和所有关键字总长成正比,见编译原理. KMP搜索算法, 由Knuth, Morris, Pratt 提出的一种在文本串中识别单个关键字的算法. 自己在学习编译有理...
KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软体; 只要安装了它, 你不用再另外安装 一大堆转码程式, 就能够顺利观赏所有特殊格式的影片了. 除此之外, KMPlayer还能够播放DVD与VCD...
来自韩国的影音全能播放器,与Mplayer一样从linux平台移植而来的Kmplayer(简称KMP)几乎可以播放您系统上所有的影音文件。...KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放
#README 这是我制作的小项目的回购。... KMP:我对经典 KMP 字符串匹配算法的实现。 01背包:我对01背包问题的实现。 通用背包:我对通用背包问题的实现 礼物的最大值:一个程序使用动态规划来找到具有最
KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软体;只要安装了它,你不用再另外安装 一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此之外,KMPlayer还能够播放DVD与...
KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放软体;只要安装了它,你不用再另外安装 一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此 之外,KMPlayer还能够播放DVD与...
KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放软体;只要安装了它,你不用再另外安装一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此 之外,KMPlayer还能够播放DVD与...
KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放软体;只要安装了它,你不用再另外安装 一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此 之外,KMPlayer还能够播放DVD与...
关于用KMP播放rmvb的方法 ... 只需要这四个文件, 就行了, 至少我还没见过不能播放的rmvb, 连1080p的高清rmvb(偶的是指环王高清rmvb )都能播放. 下面提供这四个文件, realplayer 10 版本的, 应该够用.
与 MPlayer 一样从 Linux 平台移植而来的 KMPlayer (简称KMP)几乎可以播放您系统上所有的影音文件。通过各种插件扩展 KMP 可以支持层出不穷的新格式。当然 KMPlayer 也推出了 Android 哦。KMPlayer 播放器作为一款...
个人觉得是我见过的最简单易懂的算法入门书籍。 以前搜刮过几本算法竞赛书,但是难度终归太大【好吧,其实是自己太懒了】。 略翻过教材,大多数水校的教材,大家懂的。好一点的也是那本国内的经典,不是说它写的...
KMPlayer简称 KMP,早期名叫WaSaVi播放器。作者姜龙喜(韩国),历时七年自主开发的朝鲜语多媒体图形视窗工程免费项目。KMPlayer是一套将网络上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软件;此外,...
KMPlayer简称 KMP,早期名叫WaSaVi播放器。作者姜龙喜(韩国),历时七年自主开发的朝鲜语多媒体图形视窗工程免费项目。KMPlayer是一套将网络上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软件;此外,...
KMPlayer [1] 简称 KMP,早期名叫WaSaVi播放器。作者姜龙喜(韩国),历时七年自主开发的朝鲜语多媒体图形视窗工程免费项目。KMPlayer是一套将网络上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软件;此外...
用户只需输入关键字,软件就能实时在下方显示出所有包含该关键字的字词,无需等待,瞬间即见结果。这种高效的搜索机制极大地节省了时间,尤其是在处理大型文本文件时,无论是几MB的文档,还是更庞大的文件,Text...
如Trie树(前缀树)、KMP算法,用于字符串匹配和索引构建,见poj2513和poj1961。 #### 排序 快速排序、归并排序和堆排序等,不仅用于排序,也常用于解决与逆序数相关的问题,如poj2388。 #### 并查集 用于处理集合...
答案:可以使用 KMP 算法或 Rabin-Karp 算法来解决该问题。复杂度为 O(n),其中 n 是字符串的长度。 6. 对序列 1、1、2、3、5、8、13。。。。 是 Fab.. 数列,2、3、5、13... 是 Fab.. 质数数列,因为他们与自己...