我对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;
}
虽然我没学C但是用汇编的思维去理解还是能看的懂一些学习 学过了，理解有点难度，理解完就很好 嗜血灵异狂 发表于 2011-12-3 16:01 static/image/common/back.gif
虽然我没学C但是用汇编的思维去理解还是能看的懂一些学习
后面写的很乱，你应该只看得懂前面的吧！没办法，有时候很难用人类语言去描述这些东西，虽然逻辑思维上并不是特别难！ 清/wx风 发表于 2011-12-3 16:19 static/image/common/back.gif
学过了，理解有点难度，理解完就很好
确实，起初看的让人蛋疼！ 我盯住KMP算法两天才搞清楚思路， 实现倒是不难！
KMP 算法还有一个缺陷： 只盯住模式串！
比如： asbsnkkkkkkkkkkkkkkkkkkkkkkkkkkkkk;
absslalal;
KMP 无法使时间复杂度达到最优！
KMP 我搞晕了感觉还没能真正理解是不是数学基础不好啊 next数组是怎么得出来的啊 云里雾里的 你好，顶贴赚币 好帖，顶起，这个KMP估计是串操作里的核心了{:10_279:} 为什么我把你的代码用C++的编译器运行有错误啊？
不太懂这种类型写的语言（个别代码不懂）
页:
[1]