数据结构之KMP算法

拼搏现实的明天。 2022-05-10 14:08 177阅读 0赞

一. 首先求next值

例如： 模式串 a b a a b c a c

next值 0 1 1 2 2 3 1 2

**next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。**

**1.前两位必定为0和1。**

**2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。**

**3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。**

**4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。**

**5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。**

**6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。 7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。**

二. nextval值的求法

例如主串为“aaabaaaab”、

模式串为“aaaab”

**在计算nextval之前要先弄明白，nextval是为了弥补next函数在某些情况下的缺陷而产生的。 例如主串为“aaabaaaab”、模式串为“aaaab”那么，比较的时候就会发生一些浪费的情况：比较到主串以及模式串的第四位时，发现其值并不相等，据我们观察，我们可以直接从主串的第五位开始与模式串进行比较，而事实上，却进行了几次多余的比较。使用nextval可以去除那些不必要的比较次数。**

模式串       a b a a b c a c

next值       0 1 1 2 2 3 1 2

nextval值  0 1 0 2 1 3 0 2

**1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。  **

**2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三位的nextval值为0。**

**3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。**

**4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，为1。**

**5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。**

**6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为0。**

**7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。**

**三. KMP算法**

*  **KMP算法是用来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。例如”Today is Tuesday”.中是否包含”day”，在哪些位置包含。** 
 *  **这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。**
 *  **假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A\[i-j+ 1..i\]与B\[1..j\]完全相等。 也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A\[i\]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A\[i+1\]和B\[j+1\]的关系。当A\[i+1\]=B\[j+1\]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。**
 *  **当A\[i+1\]<>B\[j+1\]，KMP的策略是调整j的位置（减小j值）使得A\[i-j+1..i\]与B\[1..j\]保持匹配且新的B\[j+1\]恰好与A\[i+1\]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。位置。**

**          i: 1 2 3 4 5 6 7 8 9 10**

**         A: a b a b a b a a b a b …**

**          B: a b a b a c b**

**           j: 1 2 3 4 5 6 7 8 9 10**

*  **从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P\[j\]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P\[j\]应该是所有满足B\[1..P\[j\]\]=B\[j-P\[j\]+1..j\]的最大值。**
 *  **事实上，有可能j到了0仍然不能满足A\[i+1\]=B\[j+1\]（比如A\[8\]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A\[i\]=B\[1\]为止。**

算法实现:

![70][]

最后的j:=P\[j\]是 为了让程序继续做 下去，因为我们有 可能找到多处匹配。 这个程序或许 比想像中的要简单， 因为对于i值的不断 增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。

[70]: /images/20220505/bdd5536a81c54c7b93ab98638c590bbe.png