p62273470 发表于 2011-12-3 15:13:32

我对kmp算法的理解

本帖最后由 p62273470 于 2011-12-3 15:13 编辑

■概念:
什么是kmp算法?
kmp算法是一种改进的字符串匹配算法。
什么是字符串匹配?
字符串匹配就是在一个大的字符串S中搜索某个字符串T的出现位置。其中,S称为文本串,T称为模式串;
字符串匹配算法有什么用?
例如:在Word等编辑器中有这样一个功能,在“查找”对话框中输入待查找的内容(常见的是查找某个字或词),系统会在整个文档中进行查找,将与待查找内容相匹配的部分高亮显示。

■先看看一般匹配算法
例子:主串S为ababcabcacbab,模式串T为abcac;
一般的匹配算法为:
i = 0;
j = 0;
while(j<模式串的长度)
{
   if(S == T)
    {
      ++i;
      ++j
    }
    else
    {
      i++;
      j = 0;
    }
    if(i>主串T的长度)
    {
      输出“字符串无法匹配!“;
      退出循环;
    }
}
//程序运行结束,i为匹配的终止位置!

①当模式串T中任何字符与主串S中的字符不相等时,整个模式串都前进一位,重新从模式串第一个字符a开始比较
匹配过程如下图:
1,ababcabcacbab
      abcac
      相等
2,ababcabcacbab
      abcac
   相等
3,ababcabcacbab
      abcac
   不相等,根据①,有步骤4,
4,ababcabcacbab
      abcac
   不相等,根据①,有步骤5
5,ababcabcacbab
          abcac
       相等
6,此处省略比较3次,因为这4次都相等
9,ababcabcacbab
            abcac
   不相等,根据①,有步骤10
10,ababcabcacbab
            abcac
       不相等,根据①,有步骤11
11,ababcabcacbab
               abcac
   不相等,根据①,有步骤12
12,ababcabcacbab
                   abcac
   相等,继续比较4次就可以得出结果了

一共需比较16次才能比较出结果
flash演示匹配过程:


分析:这种算法虽然简单,但效率太低!




■下面看看kmp算法!
kmp的思路其实不难,难的是怎样用语言来描述它!我们先看下面的内容;
我们定义一个数组next,next的大小比模式串的长度大1,当模式串为abcac时,那么next数组的大小为6,我们让next = 0,因为我们用不到next,放一边!接下来我们做下面的比较。
比较规则如下:
去掉模式串T中的第一个字符,则变为bcac,则b和b后面的所有字符为b,c和c后面所有的字符为bc,a和a后面所有的字符为bca,c和c后面所有的字符为bcac,把b,bc,bca,bcac依次和模式串abcac比较,比较的顺序是从右到左,
当符合以下条件时记录下信息:
1,当最右边的字符和模式串中的处于对齐位置的字符不相同,且其他字符和模式串中处于对齐位置上的字符相等时。
2,当最右边的字符和模式串中处于对齐位置的字符相同,且其他字符和模式串中处于对齐位置上的字符相等时。
3,取其中长度最长的!
流程如下:
模式串中的第一个字符的next值固定为0,所以next = 0;
1,比较b      
      b
      abcac
   不相等,且比较完毕,符合比较规则,记录下信息为:b为模式串中的第2(i=2)个字符,比较到第1(j=1)个字符a就完毕,则next= j(next = 1);

2,比较bc
      
   2.1    bc
               abcac
             不相等,符合比较规则,记录下信息为:c为模式串中的第3(i=3)个字符,比较到第1(j=1)个字符a。
   2.2    bc
            abcac
            不相等,但不符合比较规则,且比较完毕,取上面的信息:则next = j(next = 1);

3,比较bca
    3.1   bca
                abcac
            相等,符合规则,记录信息:a为模式串中的第4(i=4)个字符,比较到第1(j=1)个字符,next = next;
    3.2bca
            abcac
         不相等,不符合规则,不记录信息,继续;
   3.3 bca
         abcac
         不相等,不符合规则,不记录信息,取上面的信息:next = next(next = next=0);

4,比较bcac
   
   4.1bcac
                  abcac
      不相等,符合规则,记录信息:c为模式串中的第5(i=5)个字符,比较到第1(j=1)个字符a。
   4.2 bcac
               abcac
      不相等,符合规则,记录信息:c为模式串中的第5(i=5)个字符,比较到第2(j=2)个字符b。
    4.3
    4.4   此处省略,因为都不符合规则,则取4.2的,因为比较长度为2,大于4.1的,信息应为:next = j(next= 2);
所以next数组为:01102,next数组的意思是:当模式串中第j个字符和主串中第i个字符比较不等时,直接换模式串中第next和主串中的那个第i个字符比较。于是有下面的
①当模式串T中的第1个字符a与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的下一个字符比较
②当模式串T中的第2个字符b与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的当前字符比较
③当模式串T中的第3个字符c与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的当前字符比较
④当模式串T中的第4个字符a与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的下一个字符比较
⑤当模式串T中的第5个字符c与主串S中的字符不相等时,把模式串T的第二个字符b和主串S的当前字符比较
匹配流程如下:
1,ababcabcacbab
      abcac
          相等
2,ababcabcacbab
      abcac
          相等
3,ababcabcacbab
      abcac
         不相等,根据③,要把模式串T中的第一个字符a和主串S中的b比较,于是有下面的步骤4
4,ababcabcacbab
            abcac
      不相等,根据①,要把模式串T中的第一个字符a和主串S中的c比较,于是有步骤5;
5,ababcabcacbab
            abcac
       不相等,根据①,要把模式串T中的第一个字符a和主串S中的c比较,于是有下面的步骤6;
6,ababcabcacbab
                abcac
       相等,继续比较下去都相等了。
再比较4次就能得出正确结果了,所以一共只需比较10次,就算得出结果;

kmp关键在于理解得出next数组的道理!

■下面是kmp算法的代码:

#include <iostream>
#include <string.h>
using namespace std;
int Get_Next(char *p,int *next); //得到next数组
int pipei(char *s,char *t,int *next); //匹配函数
int Get_Next(char *p,int *next)
/*
指针表示模式串的数组的头指针,指针next表示next数组的头指针
*/
{

int i=1;next = 0;
int j = 0;
int len = strlen(p);
while (i < len)
{
if (j == 0 || p == p)
{
++j;
++i;
if(p != p)next = j;
else
{
next = next;
}
}
else j = next;

}

for (int h=1;h<len;h++)
{
cout<<next;
}

return 0;
}

int pipei(char *s,char *t,int *next)
/*
s表示主串的头指针,t表示模式串的头指针,next表示next数组的头指针
*/
{
int i=0,j=1;
int ilen = strlen(s);
int jlen = strlen(t);
while (j<jlen&&i<ilen)
{
if(s == t)
{
i++;
j++;
}
else
{
if (next == 0)
{
i++;
j = 1;
}
else
{
j = next-1;
}

}
}
cout<<i<<" "<<jlen<<endl;
return i+1-jlen+1;
}

void main()
{

int len = 0;
printf("请输入模式串的个数:");
cin>>len;
int *n = new int;
char *t = new char;
char s;
memset(n,0,len+1);
memset(t,0,len+2);
memset(s,0,100);
cout<<"输入模式串:";
for (int h=1; h<=len; h++)
{
cin>>t;
}
t = 'g';
Get_Next(t,n);
cout<<"next数组为:";
for (h=1;h<=len;h++)
{
cout<<n;
}

cout<<"输入主串:";
cin>>s;

int start_str = pipei(s,t,n);
cout<<endl;
cout<<"匹配的起始位置为:"<<start_str;


}





嗜血灵异狂 发表于 2011-12-3 16:01:21

虽然我没学C但是用汇编的思维去理解还是能看的懂一些学习

清/wx风 发表于 2011-12-3 16:19:54

学过了,理解有点难度,理解完就很好

p62273470 发表于 2011-12-3 16:57:57

嗜血灵异狂 发表于 2011-12-3 16:01 static/image/common/back.gif
虽然我没学C但是用汇编的思维去理解还是能看的懂一些学习

后面写的很乱,你应该只看得懂前面的吧!没办法,有时候很难用人类语言去描述这些东西,虽然逻辑思维上并不是特别难!

p62273470 发表于 2011-12-3 17:03:48

清/wx风 发表于 2011-12-3 16:19 static/image/common/back.gif
学过了,理解有点难度,理解完就很好

确实,起初看的让人蛋疼!

枫叶情缘 发表于 2012-3-26 21:05:56

我盯住KMP算法两天才搞清楚思路, 实现倒是不难!
KMP 算法还有一个缺陷: 只盯住模式串!
比如: asbsnkkkkkkkkkkkkkkkkkkkkkkkkkkkkk;
         absslalal;
KMP 无法使时间复杂度达到最优!

追忆_、流年 发表于 2012-3-28 17:48:42

KMP 我搞晕了感觉还没能真正理解是不是数学基础不好啊

追忆_、流年 发表于 2012-3-28 18:14:41

next数组是怎么得出来的啊 云里雾里的

付笑 发表于 2012-3-29 12:59:23

你好,顶贴赚币

溯影 发表于 2018-4-26 08:42:03

好帖,顶起,这个KMP估计是串操作里的核心了{:10_279:}

spark-elemtype 发表于 2018-5-15 21:26:37

为什么我把你的代码用C++的编译器运行有错误啊?

Kitty喜欢小鱼干 发表于 2018-8-11 22:13:57

不太懂这种类型写的语言(个别代码不懂)
页: [1]
查看完整版本: 我对kmp算法的理解