共计 5763 个字符，预计需要花费 15 分钟才能阅读完成。
字符贮存在 1~length 的地位上
简略模式匹配
思路：从主串的第一个地位起和模式串的第一个字符开始比拟，如果相等，则持续逐个比拟后续字符；否则从主串的第二个字符开始，再从新用上一步的办法与模式串中的字符做比拟，以此类推，直到比拟完模式串中的所有字符。若匹配胜利，则返回模式串在主串中的地位；若匹配不胜利，则返回一个可区别于主串所有地位的标记，如“0”。
int index(Str str,Str substr)
{
int i = 1,j = 1,k = 1;// 串从数组下标 1 地位开始存储，初值为 1
while(i <= str.length && j <= substr.length)
{if(str.ch[i] == substr[j])
{
i++；j++;
}
else
{
j = 1;
i = ++k;// 匹配失败，i 从主串的下一个地位开始匹配，k 贮存了主串上一次的起始地位
}
}
if(j > substr.length)
return k;
else ruturn 0;
}主串（ABABCABCACBAB)和模式串 (ABCAC) 匹配过程
KMP 算法
设主串为 s1s2…sn, 模式串为 p1p2…pm，在下面的匹配过程中，经常出现一个要害状态（表 2），其中 i 和 j 别离为主串和模式串中以后参加比拟的两个字符的下标。
模式串的前部某子串 P1P2…Pj- 1 与主串中的一个子串 Si-j+1Si-j+2…Si- 1 匹配，而 Pj 与 Si 不匹配。每当呈现这种状态时，简略模式匹配算法的做法是: 一律将 i 赋值为 i -j+2，j 赋值为 1，从新开始比拟。这个过程反映到表 2 中能够形象地示意为模式串先向后挪动一个地位，而后从第一个字符 P1 开始一一和以后主串中对应的字符做比拟；当再次发现不匹配时，反复上述过程。这样做的目标是试图打消 Si 处的不匹配，进而开始 Si+ 1 及其当前字符的比拟，使得整个过程得以推动上来。
如果在模式串后移的过程中又呈现了其前部某子串 P1P2…与主串中某子串…Si-2Si- 1 相匹配的状态，则认为这是一个提高的状态。因为通过模式串后移排除了一些不可能匹配的状态，来到了一个新的部分匹配状态，并且此时 Si 有了和模式串中对应字符匹配的可能性。为了不便表述，记表中形容的状态为 Sk，此处的新状态为 Sk+1，此时能够将简略模式匹配过程看成一个由 Sk 向 Sk+ 1 推动的过程。当由 Sk 来到 Sk+ 1 时有两种状况可能产生: 其一，S 处的不匹配被解决，从 si+ 1 持续往下比拟，若来到新的不匹配字符地位，则模式串后移寻找状态 Sk+2；其二，Si 处的不匹配依然存在，则模式串持续后移寻找状态 Sk+ 2 如此进行上来，直到失去最终后果。
阐明: 为了使上边其一与其二的表述看起来清晰工整且抓住重点，此处省略了对匹配胜利与失败这两种容易了解的状况的形容。
阐明: 模式串后移使 P1 挪动到 Si+1，即模式串整个移过 Si 的状况也认为是 Si 处的不匹配被解决。试想，如果在匹配过程中能够省略掉模式串逐步后移的过程，而从 Sk 间接跳到 Sk+1，则能够大大提高匹配效率。带着这个想法，咱们把 Sk+ 1 状态增加到表 2 中失去表 3。
察看发现，P1P2…Pj- 1 和 Si-j+1Si-j+2…Si- 1 是完全相同的，且咱们钻研的是从 Sk 跳到 Sk+1，因而，删除表 3 对于主串的一行，失去表 4。
由表 4 可知，P1P2…Pt- 1 和 Pj-t+1Pj-t+2…Pj- 1 匹配。记 P1P2..Pj- 1 为 F，记 P1P2…Pt- 1 为 FL，记 Pj-t+1Pj-t+2…Pj- 1 为 FR。所以，只需将 F 后移到使得 FL 和 FR 重合的地位（上表有色部位），即可实现 Sk 间接跳到 Sk+1。
总结个别状况：每当产生不匹配的时候，找出模式串当中的不匹配的那个字符 Pj，取其之前的子串 F =P1P2…Pj-1，将模式串后移，使 F 最先产生前部（FL）与后部（FR）相重合 的地位（见表中有色区域所示），即为模式串应后移的指标地位。
为了使问题表述得更形象，采纳了模式串后移这种剖析形式。事实上，在计算机中模式串是不会挪动的，因而须要把模式串后移转化为 j 的变动，模式串后移到某个地位可等效于 j 从新指向某地位。容易看出，j 处产生不匹配时， j 从新指向的地位恰好是 F 串中前后相重合子串的长度 +1（串 F 或 F 长度 +1）。通常咱们定义一个 next]数组，其中 j 取 1~m，m 为模式串长度，示意模式串中第 j 个字符产生不匹配时，应从 next]处的字符开始从新与主串比拟。
非凡状况:
1）模式串中的第一个字符与主串 i 地位不匹配，应从下一个地位和模式串第一个字符持续比拟。反映在从 si+ 1 与 p1 开始比拟。
2）当串 F 中不存在前后重合的局部时（不可将 F 本身视为和本身重合），则从主串中产生不匹配的字符与模式串第一个字符开始比拟，反映在表 4 - 2 中即从 s1 与 p1 开始比拟。
下边以下表中的模式串为例，介绍求数组 next 的办法。
1）当 j 等于 1 时产生不匹配，属于非凡状况 1，此时将 next[1]赋值成 0 来示意这个非凡状况。
2）当 j 等于 2 时产生不匹配，此时 F 为“”，属于非凡状况 2），即 next[2]赋值为 1。
3）当 j 等于 3 时产生不匹配，此时 F 为“AB”，属于非凡状况 2），即 next[3]赋值为 1。
4）当 j 等于 4 时产生不匹配，此时 F 为“ABA”，前部子串 A 与后部子串 A 重合，长度为 1，因而 next[4]赋值为 2（F 或 FR 长度 +1）。
5）当 j 等于 5 时产生不匹配，此时 F 为“ABAB”，前部子串 AB 与后部子串 AB 重合，长度为 2，因而 next[5]赋值为 3。
6）当 j 等于 6 时产生不匹配，此时 F 为“ABAB”，前部子串 ABA 与后部子串 ABA 最先产生重合，长度为 3，因而 next[6]赋值为 4。
7）当 j 等于 7 时产生不匹配，此时 F 为“ABABAB”，前部子串 ABAB 与后部子串 ABAB 最先产生
重合，长度为 4，因而 next[7]赋值为 5。
留神:6）和 7）中呈现了“最先 ” 字眼，以 7）为例，F 向后挪动，会产生两次前部与后部的重合，第一次是 ABAB，第二次是 AB，显然最先产生重合的是 ABAB. 之所以抉择最先的 ABAB，而不是第二次的 AB，是因为模式串是不停后移的，抉择 AB 则丢掉了一次解决不匹配的可能性，而抉择 ABAB，即便以后解决不了，则下一个状态就是 AB，不会丢掉任何解决问题的可能。这里也解释了一些参考书中提到的取最长相等前后的起因，7）中的 ABAB 或 AB 在一些参考书中称为 F 的相等前后缀（即 FL 和 FR 为 F 的相等前后缀），ABAB 是最长相等前后缀，并且很显然的是，越先产生重合的相等前后缀长度越长。
next 数组
上述办法为手工求 next 数组的办法。介绍一下实用于转换成代码的高效的求 next 数组的办法。
假如 next[j]的值已知，则 next[j+1]的求值能够分两种状况剖析。
1）若 Pj 等于 Pt，显然 next[j+1]=t+1，因为 t 为以后 F 最长相等前后缀长度（t 为 FL 和 FR 长度）。
2）若 Pj 不等于 Pt，将 Pj-t+1Pj-t+2…Pj 当作主串，P1P2…Pt 当作子串，则 又回到了由状态 Sk 找 Sk+ 1 的过程 ，所以只需将 t 赋值为 next[t]，持续进行 Pj 与 Pt 的比拟，如果满足 1）则求得 next[j+1]，不满足则反复 t 赋值为 next[t]，并比拟 Pj 与 Pt 的过程。如果在这个过程中 t 呈现等于 0 的状况，则应将 next[J+1] 赋值为 1，此处相似于上边讲到的非凡状况 2）。
阐明:Sk 间接跳到 Sk+1，也就是通常所说的简略模式匹配算法中 i 不须要回溯。
留神:MP 算法中的 i 不须要回溯这里暗藏着一个考点。i 不须要回溯意味着对于规模较大的外存中字符串的匹配操作能够分段进行，读入内存一部分进行匹配，实现之后即可写回外存确保在产生不匹配时不须要将之前写回外存的局部再次读入，缩小了 IO 操作，进步了效率，在答复 KMP 算法较之于简略模式匹配算法的劣势时，不要忘掉这一点。
算法如下
void getnext(Str substr,int next[])
{
int i = 1,j = 0;// 串从下标为 1 的地位开始存储，i 初值为 1
next[1] = 0;
while(i < substr.length)
{if(j == 0 || substr.ch[i] == sbustr[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j]// 了解这一点，回溯
}
}
失去 next 数组后，将简略模式匹配算法稍作批改就能够由状态 Sk 间接跳到 Sk+ 1 的改良算法，这就是出名的 KMP 算法，代码如下：
int KMP(Str str,Str substr,int next[])
{
int i = 1,j = 1;// 串从数组下标 1 处开始
while(i <= str.length && j <= substr.length)
{if(j == 0 || str.ch[i] == substr.ch[j])
{
++i;
++j;
}
else
j = next[j];
}
if(j > substr.length)
return i - substr.length;
else
return 0;
}KMP 算法的改良
先看一种非凡状况，见表 7。当 j 等于，产生不匹配时，因 next[5]=4，则需将 j 回溯到 4 进行比拟；又因 next[4]=3，则应将 j 回溯到 3 进行比拟…由此可见，j 须要顺次在 5、4、3、2、1 的地位上进行比拟，而模式串在 1 到 5 的地位上的字符齐全相等，因而较为聪慧的做法应该是在 j 等于 5 处产生不匹配时，间接跳过地位 1 到 4 的多余比拟，这就是 KMP 算法改良的切入点。
将上述过程推广到个别状况为：
若 Pj 等于 Pk1（k1=next[j]），则持续比拟 Pj 与 Pk2（k2=next[next[j]]），若仍相等则持续比拟上来，直到 Pj 与 Pkn 不等（kn=next[next[next[j]…]]，嵌套 n 个 next）或 kn 等于 0 时，则 next[j]重置为 kn。个别放弃 next 数组不变，而用名为 nextval 的数组来保留更新后的 next 数组，即当 Pj 与 Pkn 不等时，nextval[j]赋值为 kn。
上面通过一个例题来看一下 nextval 的推导过程。
【例】求模 ABABAAB 式串的 next 数组和 nextval 数组。
首先求出 next 数组，见表 8。
1）当 j 为 1 时，nextval[1]赋值为 0，非凡状况标记。
2）当 j 为 2 时，P2 为 B，Pk1（k1=next[2]，值为 1）为 A，两者不等，因而 nextval[2]赋值为 1。
3）当 j 为 3 时，P3 为 A，Pk1（k1=next[3]，值为 1）为 A，两者相等，因而应先判断 k2 是否为 0，而 k2 等于 next[next[3]]，值为 0，所以 nextval[3]赋值为 k2，值为 0。
留神: 步骤 3）中 P3 与 Pk1（k1=next[3]）比拟相等后，依照之前的剖析应先判断 k2 是否为 0，再让 P3 持续与 Pk2 比拟，留神到此时 nextval[next[3]]即 nextval[1]的值曾经存在，故只需间接将 nextval[3]间接赋值为 nextval[1]即可，即 nextval[3]=nextval[3]=0。
推广到个别状况为: 当 Pj 等于 Pk1（k1=next[j]）时，只需让 nextval[j]赋值为 nextval[next[j]]即可。起因有两点：
① nextval 数组是从下标 1 开始逐步往后求得的，所以在求 nextval[j]时，nextval[next[j]]必已求得。
② nextval[next[j]]为 Pj 与 Pk2 到 Pkn 比拟后果的记录，因而无须再反复比拟。
4）当 j 为 4 时，P4 为 B，Pk（k=next[4]）为 B，两者相等，因而 nextval[4]赋值为 nextval[next[4]]值为 1。
5）当 j 为 5 时，P5 为 A，Pk（k=next[5]）为 A，两者相等，因而 nextval[5]赋值为 nextval[next[5]]，值为 0。
6）当 j 为 6 时，P6 为 A，Pk（k=next[6]）为 B，两者不等，因而 nextval[6]赋值为 next[6], 值为 4。
7）当 j 为 7 时，P7 为 B，Pk（k=next[7]）为 B，两者相等，因而 nextval[7]赋值为 nextval[next[7]], 值为 1。
由此求得 nextval 数组见表 9
总结求 nextval 的个别步骤：
1）当 j 等于 1 时，nextval[j]赋值为 0，作非凡标记。
2）当 Pj 不等于 Pk 时（k=next[j]），nextval[j]赋值为 k。
3）当 Pj 等于 Pk 时（k=next[j]），nextval[j]赋值为 nextval[k]。
求 next 数组的函数 getnext()的外围代码段：
if(j == 0 || substr.ch[i] == substr.ch[j])
{
++i;
++j;
next[i] = j;//1
}
else
j = next[j];//2 在正文 1 处 next[i]已求出，且 next[0…i-1]皆已求出，则联合上边的总结，要求 nextval，能够在 1 处增加以下代码
next[i] = j;//1：i 处不匹配，应跳回 j 处
if(substr.ch[i] != substr.ch[next[i]])
nextval[i] = next[i];
else
nextval[i] = nextval[next[i]]; 显然，在正文 2 处用 next 数组来回溯 j 的代码能够用已求得的 nextval 数组代替（留神，j 往前跳，之前的 nextval 值曾经求得），批改后的代码如下：
j = nextval[j];//2 通过以上的剖析，能够将函数的 getnext()中的 next 数组用 nextval 数组代替掉，最终失去求 nextval 的代码：
void getnextval(Str substr,int nextval[])
{
int i = 1,j = 0;// 串从数组下标 1 地位开始贮存，因而初值为 1
nextval[1] = 0;
while(i < substr.length)
{if(j == 0 || substr.ch[i] == substr.ch[j])
{
++i;
++j;
if(substr.ch[i] != substr.ch[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else
j = nextval[j];
}
}
