KMP算法

1.串的模式匹配

t：目标串

s：模式串

串t的定位就是要在串s中找到一个与t相等的子串。因此串的定位查找也叫模式匹配。主要包括两种算法：Brute-Force算法和KMP算法，前者比较好理解，KMP需要认真想一下才可能明白，我也是想了好几天。下面介绍一下我对这两个算法的理解。。┭┮﹏┭┮

2.Brute-Force算法（暴力）

简称为BF算法，也称简单匹配算法，采用穷举法，从目标串s的第一个字符开始和模式串t的第一个字符进行比较，若相等，则继续逐个比较后面的字符，否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。以此类推，若模式串的每个字符都遍历过了，说明可以找到目标串s的子串和模式串相等，匹配成功，否则匹配失败。

 1 int BF(char s[],char t[])
 2 {
 3     int i=0,j=0;
 4     int len1=strlen(s),len2=strlen(t);
 5     while(i<len1&&j<len2)
 6     {
 7         if(s[i]==t[j])//当前比较的两个字符相同
 8             i++,j++;//依次比较后续的两个字符
 9         else//不相同
10             i=i-j+1,j=0;//目标串的i后退，模式串从头开始匹配
11     }
12     if(j>=len2)//t是s的子串
13         return i-len2;//t在s中的位置
14     else//匹配失败
15         return -1;
16 }

View Code

3.KMP算法

KMP算法，是D.E.Knuth，J.H.Morris和V.R.Pratt共同提出的，称之为Knuth-Morris-Pratt算法，简称KMP算法。该算法与BF算法相比有较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。KMP需要先从模式串t中提取出加速匹配的有用信息，就是算出数组next的值，这个是KMP算法中的精髓，利用KMP算法就必须会算数组next的值。数组next：代表当前字符之前的字符串中，有多大长度的相同前缀后缀，例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。其实很好理解，就是当前字符的前面几个字符和前缀相等的最大长度。

 1 void get_next(char s[],int next[])
 2 {
 3     next1[0]=-1;
 4     int k=-1,j=0;
 5     while(j<len)
 6     {
 7         if(k==-1||s[j]==s[k])
 8             next1[++j]=++k;
 9         else
10             k=next1[k];
11     }
12 }

View Code

然后就是进行目标串和模式串的匹配，当求出模式串t的next数组表示的信息后，就可以用来消除主串指针的回溯。

 1 int KMPIndex(char s,char t)
 2 {
 3     int next[MaxSize],i=0,j=0;
 4     int len1=strlen(s),len2=strlen(t);
 5     get_next(t,next);
 6     while(i<len1&&j<len2)
 7     {
 8         if(j==-1 || s[i]==t[j])
 9             i++,j++;
10         else j=next[j];
11     }
12     if(j>=len2)
13         return i-len2;
14     return -1;
15 }

View Code