KMP - String Matching

目录

​KMP主算法​

​next[]表构造算法​

KMP算法复杂度=主算法复杂度+预处理构造next[]表的复杂度​ ​

 从T中查找P,与T无关，事先给出next[]表。

 KMP主算法

next[]表构造算法

当模式串与文本串在6处发生不匹配时，由于模式串P[0,6)前三个和后三个一样，所以就不用从头开始比对，只要将第四个和文本串的这个失配节点开始比对即可.

1. 初始时，主串指针指向第0个节点，模式串指针指向哨兵。
2. P[j]=P[t]时，next[j+1]=next[j]+1，所以next表的第一项等于1。
3. if P[j+1]=P[t+1]，next[j+1]=next[j]+1；
4. P[j+1] != P[t+1], t = N [ t ], next [ j+1 +1 ] = next [ t ] + 1;
5. 比较 P[j+1] 和 P[ N [ t ] ]

KMP算法复杂度=主算法复杂度+预处理构造next[]表的复杂度

去掉那些只需要常数时间的步骤，留下if else两个步骤。