| « | November 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | | | | | | |
|
公告 |
|
| Blog信息 |
|
blog名称:FoxWolf
日志总数:127
评论数量:246
留言数量:0
访问次数:859154
建立时间:2006年5月31日 |
| |
|
 [必须掌握]朴素的模式匹配和改进的模式匹配（KMP）算法
网上资源, 软件技术
FoxWolf 发表于 2007/7/25 0:48:40 |
| 朴素的模式匹配和改进的模式匹配（KMP）算法说明 LEWISLAU前言：最近复习数据结构，以前老师讲的时候居然忽略了串。汗，我们学校的确牛B。某仁兄告诉我，KMP基本是数据结构里面难度比较大的算法了，所以掌握了它，至少从心理上给我了很大的鼓舞，但是这个算法是我询问老师才掌握的，呵呵。言规正传，开始说KMP算法。在说改进的模式匹配（KMP）算法之前我们先说朴素的模式匹配：其实很简单，就是两个字符串逐位比较。在模式匹配中：我们假定字符串P在字符串T中查找是否有匹配的。此时，称P为模式（Pattern）字符串，称T为目标（Target）字符串。OK，我一般比较喜欢以实例说明问题。T: a b d a b d a b c P: a b d a b c朴素的模式匹配算法朴素的模式匹配算法就是用P和T依次比较，即为：第一趟比较： T: a b d a b d a b c P: a b d a b c 发现第6个元素（下标为5）d和c不相等，第一趟结束，此时比较了6次（6个元素）。第二趟比较： T: a b d a b d a b c P: a b d a b c 第一个元素就不相等，第二趟结束，此时比较了1次（1个元素）。第三趟比较： T: a b d a b d a b c P: a b d a b c 第一个元素就不相等，第三趟结束，此时比较了1次（1个元素）。第四趟比较： T: a b d a b d a b c P: a b d a b c 第一个元素相等，第二个元素也相等，第三、四、五、六都相等，匹配成功，第四趟结束，此时比较了6次（6个元素）。匹配成功，共比较14次。但是这个是我们理想状态下的匹配方案，实际中字符串的长度远远不止这些。这种算法是一种带回逆的算法，成为朴素的模式匹配算法。假定：目标T长度为n，模式P长度为m，那么它的最坏情况下，会比较次数可达到： （n - m + 1）*m 次；在众多场合下m远远小于n,它的时间复杂度为O(n * m)。改进的模式匹配（KMP）算法KMP算法就是消除了朴素匹配的回逆，利用一个失效函数（failure function）替代直接的回逆。思路如下：第一趟比较： T: a b d a b d a b c P: a b d a b c 发现第6个元素（下标为5）d和c不相等。此时，进入一个P串的处理：此时取出P串， a b d a b c 因为是c不和d不匹配，去掉此项，获得a b d a b 此时判断 a b d a 是否与 b d a b 相等？ 不等，进入下一轮判断此时判断 a b d 是否与 d a b 相等？ 不等，进入下一轮判断此时判断 a b 是否与 a b 相等？ 相等，结束第一趟总体判断。（先不要急，接下来我就会说为什么这样匹配和这样匹配的用途！）以
上就是KMP的流程，为什么要这样做？在一些串中，目标串会远远长于模式串，如果每次都江模式串和目标串一一比较。此时时间复杂度当增加，而且在模式串中
会出现很多的无效匹配，相当于无用功。但是假如先在模式串中进行比较，因为模式串会远远短于目标串，所以会相当减少时间复杂度。以上是KMP的简单介绍，有机会会整理出详细算法及其优势！其他不想多说，只想说明“算法是程序的灵魂！”这一古老而经典的话！！串是一种取值受限的线性表，是数据结构中非常重要的一个成员。
在串中的运算主要有：赋值，连接，求串长，串比较，求子串（模式匹配）。
今天我主要来说一说其中最难的求子串算法，也就是串的模式匹配。我要讲两种不同的求子串的方法：一种是普素的模式匹配；另一种是改进的模式匹配（KMP匹配算法）。我用的是C语言的伪代码。
普素的模式匹配：
S串：abcacdghi
T串：acd
求T串是否为S串的子串，如果是返回T串在S串中的位置，如果否返回-1。
算法核心逻辑分析：我们要用T串分别与S串的每一个字符为起始字符的子串来比较。也就是说我们先拿T串的第一个字符与S串的第一个字符相比较，如果相同的
话，我们拿T,S的第二个字符来比较，如果不同的话S串的比较位置从第二个字符开始，T串的比较位置仍从第一个字符开始。由这个思路向下分析，我们不难想
到整个比较过程是这样的：每次比较成功双串指针后移一个字符继续这一轮比较；每次比较失败S串回到上次开始比较字符的下一字符，而T串回到起始位置即第一
个字符开始下一轮比较。
如果我们的比较过程到了T串的结尾仍未发现不同那么T串就是S串的子串，其位置就是当前S串的位置减去T串的长度。如果我们一直比较到S串结尾T串也未比较到结尾字符就说明整个S串中没与T串相匹配的子串，就要返回-1。
上面东西你只要理解了整个比较流程就行了。没必要硬扣。下面我们用上面的实例定量分析你就明白了。
S：abcacdghi\0
T：acd\0
其中'\0'为串的结束符因为在C语言中的串就是有一个结束符，虽然串在逻辑上不包含它但是它是实际存在的。所以我们的算法要考虑它。但这并不会影响到我们的思路。
下面开始，我们设S的字符指针是i；T的字符指针是j；
第一轮比较： i=1;
j=1;
相同 'a'=='a'；
指针后移 i++; //2
j++; //2
不同 'b'!='c';
第二轮比较： i=2; //i-j+2
j=1;
不同 'b'!='a';
第三轮比较： i=3; //i-j+2
j=1;
不同 'c'!='a';
第四轮比较 i=4; //i-j+2
j=1;
相同 'a'=='a';
指针后移 i++; //5
j++; //2
相同 'c'=='c';
指针后移 i++; //6
j++; //3
相同 'd'=='d';
指针后移 i++; //7
j++; //4
到T串结束符 T[j-1] =='\0';//我们比较时第一个字符定位为1，而字符数组第一个字符为0
返回T在S中的位置 p=i-strlen(T);//7-3=4
由以上的实例我们可以规纳出如下结论：当一轮比较失败开始下一轮时S串的比较位置应回到i-j+2;当然这是我将第一个字符定位为1的结果，如果我们把第一个字符定位为0，就应回位至：i-j+1;而T串每一轮比较开始都要回位到第一个字符。
我们也发现，最终的比较结果就是两种情况，一种是T是S的子串，匹配成功；
一种是T不是S的子串，匹配失败。我们同时也发现，只有当T串的指针被移到结束符上时匹配才会成功；这也就是我们退出比较过程的一个条件。也就是说当T串的指针指向了结束符时就应该以匹配成功退出比较了。那么如果T串本就不是S串的子串我们又怎么结束比较呢？不难看出，当i指
向S串的结束符时，不管T是否是S的子串我们都无法再比较下去了。因为我们已经遍历了S串了。所以i指向S串的结束符，也是结束比较的一个条件。那么既然
两个条件都可以用来结束比较，所以我们在结束比较以后并不知道是否已经成功匹配。这就需要判断是怎么结束的比较。如果是因为T串的指针到了结束符那就一定
匹配成功了，这是没错的。你一定会接着说如果S串的指针到了结束符就匹配失败了，这就大错了。因为有一种情况就是T，S的指针同时到了结束符上。这种情况
是匹配成功的呀。所以这里一定要注意！判断匹配失败的条件是比较结束，同时T串的指针并没指到结束符上。这里一定要想明白呀！
还有一点，就是我们这里所讲的是从S串的第一个字符开始求T串的子串，而实际应用中开始匹配的位置并一定是第一个字符，所以已知的量就应有一个开始匹配位置：pos；我们前面的分析就是当POS=1时的情况。
下面我就给出这种算法的伪代码：
int Index(char * s, char *t, int pos){/*若t串是s串从pos位置开始的串的子串返回在s串的位置，否则返回-1*/ int i, j; i=pos; j=1; while(t[j-1] != '\0' && s[i-1] != '\0') { if(t[j-1] == s[i-1]) { i++; j++; }else { i = i-j+2; j = 1; } }/*endwhlie*/ if(t[j-1] == '\0') { return i-strlen(t);/*＃i nclude <string.h>*/ } return -1;}
上面的算法我们是当一次比较字符相同时，i 和j同时向后推1即i++;j++;
这里我们也可以变化一下，因为这时候i
和j总是同时增加的。所以我们在一轮匹配失败的时还要回退S串的i指针，很麻烦，而且那个算式也要想半天才能通。那么我们可以在一次比较字符相同时只j+
+，因为T串在每一轮比较都从1开始，而S串和T串在比较相同时指针都要同时向后移动一个字符。我们就可以用j的值和i的值得到S串将要参加比较的位置指
针---i+j-1;又因为我们串的第一个字符定位为1，而字符数组定位为0，所以在数组下标中还要再减去1，即i+j-2。
这样当我们在一轮比较有不同的字符时就不用回退i了,因为i并未随j一起增加。只需将i向后移1即:i++;下面给出代码：
int Index(char * s, char *t, int pos){/*若t串是s串从pos位置开始的串的子串返回在s串的位置，否则返回-1*/ int i, j; i=pos; j=1; while(t[j-1] != '\0' && s[i+j-2] != '\0') { if(t[j-1] == s[i+j-2]) { j++; }else { i ++; j = 1; } }/*endwhlie*/ if(t[j-1] == '\0') { return i; } return -1;}
上
面有一点要注意的就是比较结束的条件也要有一点点变化了，还有返回值。为什么呢？因为我们的每轮比较时i不发生变化，是由j的变化来推动S串的指针后移，
所以用来判定是否比较到S串的结尾的表达式就是i+j,因为字符数组的下标从0开始所以i,j都应减1，最后表达式应是i+j-2;而在匹配成功之时i的
位置正好是这一轮比较的开始位置，所以也就是反回值了。
我们这时又发现了一点问题，就是我们有时没有必要把比较持续到以S串的最后一个字符开始的子串。因为除非T串是一个字符的串，否则S串的长度到那时根本就
不够长了。那么我们就针对第二种算法做改进吧，按我们的想法，当i的值使Si,Si+1......Sstrlen(s)的字符个数小于T串的长度时就可
以停止比较了。那么我们给出这个算法的代码：
int Index(char * s, char *t, int pos){/*若t串是s串从pos位置开始的串的子串返回在s串的位置，否则返回-1*/ int i, j; i=pos; j=1; while(t[j-1] != '\0' && (strlen(s)-i+1) >= strlen(t)) /*改动之处*/ { if(t[j-1] == s[i+j-2]) { j++; }else { i ++; j = 1; } }/*endwhlie*/ if(t[j-1] == '\0') { return i; } return -1;}
如果是针对第一种算法来修改就麻烦一些，因为在每一轮比较中i也
会移动，所以如果用i来进行这个判断就只有在一轮比较开始时i的值才是可以的，而在一轮的比较过程中i的值是可以到达S串的最后一个字符的。所以我们如果
也像修改第二种算法那样i就永远也不会到达S串的结尾，会出错的。可是我们知道i和j在一轮比较中是都同时后移的，所以我们可以用j的值辅助i来屏蔽这个
错误的产生。我们给出算法如下：
int Index(char * s, char *t, int pos){/*若t串是s串从pos位置开始的串的子串返回在s串的位置，否则返回-1*/ int i, j; i=pos; j=1; while(t[j-1] != '\0' && (i+j-1) <= strlen(s)) /*改动之处*/ { if(t[j-1] == s[i-1]) { i++; j++; }else { i = i-j+2; j = 1; } }/*endwhlie*/ if(t[j-1] == '\0') { return i-strlen(t);/*＃i nclude <string.h>*/ } return -1;}
看来每一种算法也可以写出不同的代码来，真奇妙啊！！KMP:模式串p[n],主串t[n]。整个算法的时间复杂度为O(m+n)，其中求next[]的时间复杂的为O(m)，优于朴素模式匹配算法的O(m*n)。下面是我写的C代码：void getnext(char p[],int next[]){ int i,j; next[0]=-1; i=0;j=-1; while(i<(int)strlen(p)) { if(j==-1||p[i]==p[j]) { i++; j++; next[i]=j; } else j=next[j]; } for(i=0;i<(int)strlen(p);i++) printf("%d ",next[i]); printf("\n");} int kmp(char t[],char p[]){ int i,j; i=0;j=0; while(i<(int)strlen(t)&&j<(int)strlen(p)) { if(j==-1||t[i]==p[j]) { i++; j++; } else j=next[j]; } if(j==(int)strlen(p)) return(i-(int)strlen(p)); else return (-1);}/* *作者JunyiSun @ CCNU *E-MAIL:CCNUSJY@GMAIL.COM *KMP算法C代码描述*/ #include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX_S 101 /*主串的长度最大值为100*/#define MAX_P 21 /*模式串的长度最大值为20*/ char s[MAX_S],p[MAX_P]; /*s为主串，p为模式串*/int nextv[MAX_P]; /*p的nextv数组*/ void init_nextv(){ int i=0,j=-1; int p_len; /*模式串的长度*/ p_len=strlen(p); nextv[0]=-1; while(i<p_len-1){ if(j==-1 || p[i]==p[j]){ ++i;++j; if(p[i]!=p[j])nextv[i]=j; else nextv[i]=nextv[j]; } else j=nextv[j]; }} int kmp(){ int i=0,j=0,s_len,p_len; s_len=strlen(s); p_len=strlen(p); while(i<s_len && j<p_len){ if(j==-1 || s[i]==p[j]){ i++;j++; } else j=nextv[j]; } if(j==p_len)return i-p_len; else return -1;} int main(){ int index=0; printf("请输入主串:"); scanf("%s",s); printf("请输入子串:"); scanf("%s",p); init_nextv(); index=kmp(); if(index!=-1) printf("匹配成功，匹配位置%d\n",index); else printf("匹配失败\n"); system("pause"); return 0;} |
|
|
回复:朴素的模式匹配和改进的模式匹配（KMP）算法
网上资源, 软件技术
ds(游客)发表评论于2007/9/4 20:18:47 |
|
» 1 »
|