马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 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[j]）
{
++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演示匹配过程：
字符串匹配一般过程.rar
(3.88 KB, 下载次数: 25)
分析：这种算法虽然简单，但效率太低！
■下面看看kmp算法！
kmp的思路其实不难，难的是怎样用语言来描述它！我们先看下面的内容；
我们定义一个数组next，next的大小比模式串的长度大1，当模式串为abcac时，那么next数组的大小为6，我们让next[0] = 0，因为我们用不到next[0]，放一边！接下来我们做下面的比较。
比较规则如下：
去掉模式串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[1] = 0;
1，比较b
b
abcac
不相等，且比较完毕，符合比较规则，记录下信息为：b为模式串中的第2（i=2）个字符，比较到第1（j=1）个字符a就完毕，则next= j（next[2] = 1）;
2，比较bc
2.1 bc
abcac
不相等，符合比较规则，记录下信息为：c为模式串中的第3（i=3）个字符，比较到第1（j=1）个字符a。
2.2 bc
abcac
不相等，但不符合比较规则，且比较完毕，取上面的信息：则next = j（next[3] = 1）;
3，比较bca
3.1 bca
abcac
相等，符合规则，记录信息:a为模式串中的第4（i=4）个字符，比较到第1(j=1)个字符，next[4] = next[1]；
3.2 bca
abcac
不相等，不符合规则，不记录信息，继续；
3.3 bca
abcac
不相等，不符合规则，不记录信息，取上面的信息：next = next[j]（next[4] = next[1]=0）;
4，比较bcac
4.1 bcac
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[5 ]= 2）;
所以next数组为:01102，next数组的意思是：当模式串中第j个字符和主串中第i个字符比较不等时，直接换模式串中第next[j]和主串中的那个第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[1] = 0;
int j = 0;
int len = strlen(p);
while (i < len)
{
if (j == 0 || p[i] == p[j])
{
++j;
++i;
if(p[i] != p[j])next[i] = j;
else
{
next[i] = next[j];
}
}
else j = next[j];
}
for (int h=1;h<len;h++)
{
cout<<next[h];
}
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[i] == t[j])
{
i++;
j++;
}
else
{
if (next[j] == 0)
{
i++;
j = 1;
}
else
{
j = next[j]-1;
}
}
}
cout<<i<<" "<<jlen<<endl;
return i+1-jlen+1;
}
void main()
{
int len = 0;
printf("请输入模式串的个数:");
cin>>len;
int *n = new int[len+1];
char *t = new char[len + 2];
char s[100];
memset(n,0,len+1);
memset(t,0,len+2);
memset(s,0,100);
cout<<"输入模式串:";
for (int h=1; h<=len; h++)
{
cin>>t[h];
}
t[0] = 'g';
Get_Next(t,n);
cout<<"next数组为：";
for (h=1;h<=len;h++)
{
cout<<n[h];
}
cout<<"输入主串：";
cin>>s;
int start_str = pipei(s,t,n);
cout<<endl;
cout<<"匹配的起始位置为:"<<start_str;
}
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2011-12-3 15:13:32
置顶卡
千斤顶
显身卡
楼主
发表于 2018-8-11 22:13:57