作者：Grey
原文地址: KMP算法解决字符串匹配问题
假设字符串str长度为N，字符串match长度为M，<code>M <= N</code>, 想确定str中是否有某个子串是等于match的。返回和match匹配的字符串的首字母在str的位置，如果不匹配，则返回-1
OJ可参考：LeetCode 28. 实现 strStr()
从str串中每个位置开始匹配match串，时间复杂度<code>O(M*N)</code>
KMP算法可以用<code>O(N)</code>时间复杂度解决上述问题。
我们规定数组中每个位置的一个指标，这个指标定义为
这个位置之前的字符前缀和后缀的匹配长度，不要取得整体。
例如: <code>ababk</code> 这个字符串，<code>k</code>位置的指标为2, 因为<code>k</code>之前位置的字符串为<code>abab</code>
前缀<code>ab</code> 等于 后缀<code>ab</code>，长度为2，下标为3的<code>b</code>的指标为1，因为<code>b</code>之前的字符串<code>aba</code> ,前缀<code>a</code> 等于后缀<code>a</code>, 长度为1。
人为规定：<code>0</code>位置的指标是-1，<code>1</code>位置的指标0
假设match串中每个位置我们都已经求得了这个指标值，放在了一个<code>next</code>数组中，这个数组有助于我们加速整个匹配过程。
我们假设在某个时刻，匹配的到的字符如下
其中str的<code>i..j</code>一直可以匹配上match串的<code>0...m</code>, str中的<code>x</code>位置和match串中的<code>y</code>位置第一次匹配不上。如果使用暴力方法，此时我们需要从str的<code>i+1</code>位置重新开始匹配match串的<code>k</code>位置，而KMP算法，利用next数组，可以加速这一匹配过程，具体流程是，依据上例，我们可以得到<code>y</code>位置的<code>next</code>数组信息，假设<code>y</code>的<code>next</code>数组信息是2，如下图
如果<code>y</code>的<code>next</code>数组信息是2，那么<code>0...k</code> 这一段完全等于<code>f...m</code>这一段，那么对于match来说，当<code>y</code>位置匹配不上<code>x</code>位置以后, 可以直接让<code>x</code>位置匹配<code>y</code>的<code>next</code>数组位置<code>p</code>上的值，如下图
如果匹配上了，则<code>x</code>来到下一个位置，<code>p</code>来到下一个位置继续匹配，如果再次匹配不上，假设<code>p</code>位置的next数组值为0, 则继续用<code>x</code>匹配<code>p</code>的<code>next</code>数组位置<code>0</code>位置上的值，如下图
如果<code>x</code>位置的值依旧不等于<code>0</code>位置的值，则宣告本次匹配失败，str串来到<code>x</code>下一个位置，match串从<code>0</code>位置开始继续匹配。
<code>next</code>数组的求解是KMP算法中最关键的一步，要快速求解<code>next</code>数组，需要做到当我们求<code>i</code>位置的<code>next</code>信息时，能通过<code>i-1</code>的<code>next</code>数组信息加速求得,如下图
当我们求<code>i</code>位置的<code>next</code>信息时，假设<code>j</code>位置的<code>next</code>信息为6，则表示
<code>m...n</code>这一段字符串等于<code>s...t</code>这一段字符，此时可以得出一个结论，如果：
<code>x</code>位置上的字符等于<code>j</code>位置上的字符，那么<code>i</code>位置上的<code>next</code>信息为<code>j</code>位置上的<code>next</code>信息加1，即为7。如果不等，则继续看<code>x</code>位置上的<code>next</code>信息，假设为2，则有：
此时，判断<code>q</code>位置的值是否等于<code>j</code>位置的值，如果相等，那么<code>i</code>位置上的<code>next</code>信息为<code>x</code>位置上的<code>next</code>信息加1，即为3，如果不等，则继续看<code>q</code>位置上的<code>next</code>信息，假设为1，那么有
此时，判断<code>p</code>位置的值是否等于<code>j</code>位置的值，如果相等，那么<code>i</code>位置上的<code>next</code>信息为<code>q</code>位置上的<code>next</code>信息加1，即为2，如果不等，则继续如上逻辑，如果都没有匹配上<code>j</code>位置的值，则<code>i</code>位置的<code>next</code>信息为0。
<code>next</code>数组的求解流程时间复杂度显然为<code>O(N)</code>，现在估计主流程的复杂度，主流程中，<code>x</code>能取得的最大值为str字符串的长度N，定义一个变量<code>x-y</code>,能取得的最大值不可能超过N（即当x = N，y=0时候），在主流程的wile循环中，有三个分支
我们考虑这三个分支对于<code>y</code>和<code>y - x</code>变化范围的影响
分支
y
y - x
x++; y++
推高
不变
x = next[x]
y++
如上分析，<code>y</code>和<code>y-x</code>都不可能降低，且三个分支只能中一个，所以，而<code>y</code>和<code>y-x</code>的最大值均为N，所有分支执行总推高的次数不可能超过2N。即得出主流程的复杂度<code>O(N)</code>
思路
将这个字符串拼接一下, 比如原始串为：123456，拼接成：123456123456
如果匹配的字符串是这个拼接的字符串的子串，则互为旋转词。
先将两棵树分别序列化为数组A和数组B，如果B是A的子串，那么A对应的二叉树中一定有某个子树的结构和B对应的二叉树完全一样。
算法和数据结构笔记
算法和数据结构体系班-左程云