KMP算法的问题与心得（非原理介绍）

KMP算法的问题与心得（非原理介绍）

前提：假设字符串起始索引为1。主串长度为m，索引为i；模式串长度为n，索引为j。

一、如何计算主体函数（已知next数组）的时间复杂度

KMP算法无非就两个部分：i与j共同增加1；i不动，j减少（即j = next[j]）。
时间复杂度的求解需要知道上述两个运行次数为无穷大的语句相加的结果。

1.i与j共同加1

这种情况是遇到相匹配或模式串第1位于主串第i位不匹配导致的。
i从1增长到主串结尾m，因此该语句最多执行m次。

2.i不动，j减少

这种情况是遇到模式串的第j位与主串的i位不匹配导致的。
j每次减少的量若最少会导致操作步骤的最多。因此j每次减少1，操作步骤会最多。
j的每次减一消耗的是上述的i加一操作。
因此j减1最多的执行次数与操作一一致，m次

总结

因此俩个操作之和就是2m次。时间复杂度为其基本同阶无穷大，即O(m)。

二、next与nextval数组的手算求法

1.next数组

首项与第二项填0与1。后面每一项找到当前项前面的字符串的最长相同前后缀的前缀，该前缀的后面一位的索引即该该项的next值。

2.nextval数组

写出next数组。接下来开始nextval手算。
第一项填0，后面每一项比对该项与next[该项下标]对应的字符是否相等，
若不相等，直接填next；若相等，填nextval[next[该项下标]]