也许从KMP算法能获得一些如何减少重复判断的启发
字符串匹配算法之最，kmp算法。
在全集串中寻找目标串的出现位置。
思路。
思考那些是根本就不可能匹配的操作，跳过他们，减少机械地判断次数。
先说用法。
首先，从目标串找规律。
index 0 1 2 3 4 5 6
no. d1 d2 d3 d4 d5 d6 d7
content a b a c a b a
思考，将内容 (content) 依次拆成子串，算一些数，至于意义，一会儿再说。
首先，将子串右移，尝试并记录 “右移几步” 和 “那样能产生的不少于1个字符的字符匹配量”。
- a
a 与自身 a，右挪 0 步就能匹配自身，匹配量为 1 个字符。 - ab
ab 与自身 ab，右挪 0 步就能匹配自身，匹配量为 2 个字符。 - aba
aba 与自身 aba，右挪 0 步就能匹配自身，匹配量为 3 个字符。
aba 与自身 aba，右挪 2 步就能匹配自身，匹配量为 1 个字符。 - abac
abac 与自身 abac，右挪 0 步就能匹配自身，匹配量为 4 个字符。 - abaca
abaca 与自身 abaca，右挪 0 步就能匹配自身，匹配量为 5 个字符。
abaca 与自身 abaca，右挪 4 步就能匹配自身，匹配量为 1 个字符。 - abacab
abacab 与自身 abacab，右挪 0 步就能匹配自身，匹配量为 6 个字符。
abacab 与自身 abacab，右挪 4 步就能匹配自身，匹配量为 2 个字符。 - abacaba
abacaba 与自身 abacaba，右挪 0 步就能匹配自身，匹配量为 7 个字符。
abacaba 与自身 abacaba，右挪 4 步就能匹配自身，匹配量为 3 个字符。
我们除去那些若有有多种匹配方案的本身与本身匹配的情况，则有：
- a
a 与自身 a，右挪 0 步就能匹配自身，匹配量为 1 个字符。 - ab
ab 与自身 ab，右挪 0 步就能匹配自身，匹配量为 2 个字符。 - aba
aba 与自身 aba，右挪 2 步就能匹配自身，匹配量为 1 个字符。 - abac
abac 与自身 abac，右挪 0 步就能匹配自身，匹配量为 4 个字符。 - abaca
abaca 与自身 abaca，右挪 4 步就能匹配自身，匹配量为 1 个字符。 - abacab
abacab 与自身 abacab，右挪 4 步就能匹配自身，匹配量为 2 个字符。 - abacaba
abacaba 与自身 abacaba，右挪 4 步就能匹配自身，匹配量为 3 个字符。
index 0 1 2 3 4 5 6
no. d1 d2 d3 d4 d5 d6 d7
【content】 【a b a c a b a】
rGo(右移几步实现匹配) 0 0 2 0 4 4 4
val 0 0 d1 0 d1 d2 d3
——注释：右移非零最少几步能实现匹配。右移的部数越少，匹配量越大，这两者并不冲突。因为我们所说的匹配不是镜面对称，而是目标串自身前、后缀子字符串的相同。
令 val[d1] = 0，计算每个 content 的 val 值。方法是：
用每个 content 的前一个 content 对应的 val值+1，找与该结果相等的 no. 值的 content，看相不相同。相同写 no 值。
不相同就和 content[d1] 比，相同写1，不相同写0。
content 的 val 值，表示的是 到该 content 为止的目标串子串进行自身匹配时，该 content 与 no.值等于该val值的那个 content 相同（匹配）。
之所以用 前一个 content 对应的 val值+1，是因为到前面那个 content 为止，那个 content 已经和 与它val值相等的no. 的content 最大量匹配了，且之前的也都匹配了。新加进来的，就和已经匹配完的前缀字符串后面的一个字符比比看就知道是否能继续匹配了。不相等，那么功亏一篑，直接和首位 content[d1] 比较吧。
不能往前跑，是因为，……好乱呀。
(a1 c1 g1 m1) (a2 c2 g2 m2) m
m与a2不同，要是往前跑，
就算m与m1相同，m2与g1也不相同阿。
(a1 c1 m1 m1) (a2 c2 m2 m2) m
0 0 0 0 1 2 3 4
(a1 c1 m1 m1)
(a2 c2 m2 m2) m
前m2与c1也不相同阿。
(m1 m1 m1 m1)
(a2 m2 m2 m2) m
(m m m m) (a m m m) m
0 1 2 3 0 1 2 3 4
如果最后一位m失配了，就将子串向右挪 9-4=5 格，即从 第4格 挪到 第9格，需要挪动5格。（第4格挪到第5格需要挪动1格）
不与首位比，只是往前跑的话，你不能确定前几位都是匹配的。
如果前几位都相等的话，那毋庸置疑，这一位就是4，不过那已经改变问题了。
事实上，你不能确定往前跑一步，之前的前几位都是匹配的。
挪动的时候，就知道自己和自己能匹配的最小步数是多少，之前的都不用判断了，根本无法匹配。
挪到自己和自己匹配的地方也没用，因为已经失配了，所以，继续向右推一个格。
接下来是关键，已知在 第i位(no.值) 失配，即 前i-1位 皆配。
已知 第i位(no.值) 与到该失配位为止的子串自身的 第val位 相同。
欲把 第val位 挪至 第i位，整串需挪 i-val 位，即是 rGo 的值。
此时，仍是失配的状态，所以，再向右移一格。
为什么除了挪动后失配，前面省掉的步骤也一定是失配的呢？
因为对 与到该失配位为止的子串 的 自身与自身的匹配情况，我们已经研究过了。
既然在 第i位(no.值) 失配，即 前i-1位 皆配。挪动，也就相当于在失配位前的子串后面加一个新字符，再探讨它向右最少移动几步能匹配。
若能匹配，则向右移动的越少，（能）匹配（的）量越大。
对了，就是 {{{{{ 该子串第一次出现首尾自身匹配的情况 }}}}}。这么说才对。
因为kmp是跳步的算法，你必须保证不能漏。所以要一直想着，
——若只向右移动一位，是不是有可能就成了呢？——
然后不断改全集串，验证一些猜想。
挪动 失配位dID-失配位val 自身才能再次头一回与自身在已匹配的部分匹配。
这是个曾经沧海难为水，越吃胆子越大的算法。
