`
yuexiaodong
  • 浏览: 70342 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

KMP之我见

阅读更多

传统的简单匹配算法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]个字符)
模式值函数的定义:
1next[0]= -1 意义:任何串的第一个字符的模式值规定为-1
2next[j]= -1   意义:模式串T中下标为j的字符,如果与首字符
相同,且j的前面的j—k个字符与开头的j—k
个字符不等(或者相等但T[k]==T[j])(1k<j)。
如:T=”abCabCad”  next[6]=-1,因T[3]=T[6]
3next[j]=k    意义:模式串T中下标为j的字符,如果j的前面k
字符与开头的k个字符相等,且T[j] != T[k] 1k<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].1k<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算法的Next及NextVal序列求解

    今天遇到一个KMP算法的题,以前根本没见过,上网查了好多关于KMP,但是讲的都不是很清楚,看的一头雾水,然后就自己研究做出了一个小程序,附上了相关算法解释!希望这个小程序可以帮助大家很好的了解KMP算法Next及...

    Aho-Corasick 算法 和 KMP搜索算法

    Aho-Corasick 算法, 用于从文本串中识别一组关键字,所需的时间和文本长度和所有关键字总长成正比,见编译原理. KMP搜索算法, 由Knuth, Morris, Pratt 提出的一种在文本串中识别单个关键字的算法. 自己在学习编译有理...

    Kmplayerv2.9.4.1435Pre2莫尼卡带插件安装版

    KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软体; 只要安装了它, 你不用再另外安装 一大堆转码程式, 就能够顺利观赏所有特殊格式的影片了. 除此之外, KMPlayer还能够播放DVD与VCD...

    The_KMPlayer_1436

    来自韩国的影音全能播放器,与Mplayer一样从linux平台移植而来的Kmplayer(简称KMP)几乎可以播放您系统上所有的影音文件。...KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放

    SmallProjects:我对有用算法、数据结构和其他编码问题的实现

    #README 这是我制作的小项目的回购。... KMP:我对经典 KMP 字符串匹配算法的实现。 01背包:我对01背包问题的实现。 通用背包:我对通用背包问题的实现 礼物的最大值:一个程序使用动态规划来找到具有最

    KMPlayer 1434(当前最新版)

    KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软体;只要安装了它,你不用再另外安装 一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此之外,KMPlayer还能够播放DVD与...

    KMPlayer播放器

    KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放软体;只要安装了它,你不用再另外安装 一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此 之外,KMPlayer还能够播放DVD与...

    Kmplayer2010绿色免安装版

    KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放软体;只要安装了它,你不用再另外安装一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此 之外,KMPlayer还能够播放DVD与...

    kmplayer 2.9.4.1435

    KMPlayer是一套将网路上所有能见得到的解码程式(Codec)全部 收集于一身的影音播放软体;只要安装了它,你不用再另外安装 一大堆转码程式,就能够顺利观赏所有特殊格式的影片了。除此 之外,KMPlayer还能够播放DVD与...

    kmplayer播放rmvb的dll文件

    关于用KMP播放rmvb的方法 ... 只需要这四个文件, 就行了, 至少我还没见过不能播放的rmvb, 连1080p的高清rmvb(偶的是指环王高清rmvb )都能播放. 下面提供这四个文件, realplayer 10 版本的, 应该够用.

    来自韩国的影音全能播放器 KMPlayer 4.2.2.45 x64 中文多语免费版.zip

    与 MPlayer 一样从 Linux 平台移植而来的 KMPlayer (简称KMP)几乎可以播放您系统上所有的影音文件。通过各种插件扩展 KMP 可以支持层出不穷的新格式。当然 KMPlayer 也推出了 Android 哦。KMPlayer 播放器作为一款...

    算法 第四版

    个人觉得是我见过的最简单易懂的算法入门书籍。 以前搜刮过几本算法竞赛书,但是难度终归太大【好吧,其实是自己太懒了】。 略翻过教材,大多数水校的教材,大家懂的。好一点的也是那本国内的经典,不是说它写的...

    KMPlayer_3.5.0.77

    KMPlayer简称 KMP,早期名叫WaSaVi播放器。作者姜龙喜(韩国),历时七年自主开发的朝鲜语多媒体图形视窗工程免费项目。KMPlayer是一套将网络上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软件;此外,...

    最好用的视频播放器KMPlayer3.0

    KMPlayer简称 KMP,早期名叫WaSaVi播放器。作者姜龙喜(韩国),历时七年自主开发的朝鲜语多媒体图形视窗工程免费项目。KMPlayer是一套将网络上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软件;此外,...

    KMPlayer_4.2.2.8.exe

    KMPlayer [1] 简称 KMP,早期名叫WaSaVi播放器。作者姜龙喜(韩国),历时七年自主开发的朝鲜语多媒体图形视窗工程免费项目。KMPlayer是一套将网络上所有能见得到的解码程式(Codec)全部收集于一身的影音播放软件;此外...

    文本快速搜索TextFilter 支持任意语言

    用户只需输入关键字,软件就能实时在下方显示出所有包含该关键字的字词,无需等待,瞬间即见结果。这种高效的搜索机制极大地节省了时间,尤其是在处理大型文本文件时,无论是几MB的文档,还是更庞大的文件,Text...

    poj各种分类

    如Trie树(前缀树)、KMP算法,用于字符串匹配和索引构建,见poj2513和poj1961。 #### 排序 快速排序、归并排序和堆排序等,不仅用于排序,也常用于解决与逆序数相关的问题,如poj2388。 #### 并查集 用于处理集合...

    c++面试题集锦

    答案:可以使用 KMP 算法或 Rabin-Karp 算法来解决该问题。复杂度为 O(n),其中 n 是字符串的长度。 6. 对序列 1、1、2、3、5、8、13。。。。 是 Fab.. 数列,2、3、5、13... 是 Fab.. 质数数列,因为他们与自己...

Global site tag (gtag.js) - Google Analytics