1. 朴素的字符串匹配方法
1.1 比较过程
以主串T为基础，根据索引i对每个字符进行遍历，依次与目标串P的每个索引j的字符进行匹配。若字符相同，则两索引均后移，继续匹配；若不相同，则j恢复为0，从头开始，i回溯到开始成功匹配时索引的下一位。
1.2 比较结果
遍历索引i结束之后，若此时j已经达到目标串P的最后，则证明目标串的所有字符均匹配成功，目标串在主串中的位置即length(T) - j；否则匹配失败，P不是T的子串。
1.3 主要实现
NSInteger findIndex(const char *sourceStr, const char *targetStr) {
// 获取二者长度
NSInteger sourceLength = strlen(sourceStr);
NSInteger targetLength = strlen(targetStr);
NSInteger i = 0; // 主串索引
NSInteger j = 0; // 目标串索引
while ((i < sourceLength) && (j < targetLength)) {
if (sourceStr[i] == targetStr[j]) {
// 字符相同，继续向后
i += 1;
j += 1;
} else {
// 字符不同
// 主串索引恢复到开始成功匹配时的下一位
i = i - j + 1;
// 目标串索引恢复到头
j = 0;
}
}
// 注：这里的大于只是防止最后一位匹配成功后的+1操作
if (j >= targetLength) {
// 主串的最终遍历索引 前移 目标串长度，即为子串的起始位置
return i - targetLength;
}
return NSNotFound;
}
2. KMP的字符串匹配方法
KMP方法的作用主要是去掉了一些可避免的比较，提高了匹配效率。
2.1 匹配过程
KMP的主要匹配过程与朴素一致，都是字符依次比较。优化点是在字符匹配失败时，尽量让主串T的索引i不回溯，目标串的索引j回溯到需要的位置（而不是直接到0）。从而达到减少比较次数的目的。
如上所述，KMP的核心就是在任意位置匹配失败时，目标串的索引j回溯到的位置。
我们将所有回溯位置的信息保存到数组next中，故最终目的就是计算出next数组的完整信息。
2.1.1 匹配表（Partial Match Table）
要说next数组，就先要了解匹配表PMT的含义。以字符串“abababca”为例，其匹配表如下：
image
其中，value行即为PMT的值。其意义是什么呢？
value的值是子串中前缀与后缀集合中，最长的公共子串的长度。例如，下表分别为当index为2和5时，value的得出过程：
| 索引 | 子串 | 前缀集合 | 后缀集合 | 交集 | 最长子串长度 |
|---|---|---|---|---|---|
| 2 | “aba” | {“a”，“ab”} | {“ba”，“a”} | {“a”} | 1 |
| 5 | “ababab” | {“a”，“ab”，“aba”，“abab”，“ababa”} | {“b”，“ab”，“bab”，“abab”，“babab”} | {“ab”，“abab”} | 4 |
故目标字符串有几位，就会有几个PMT中对应的值。
2.1.2 next表（PMT表的修改形式）
先抛图（主串“ababababca”和子串“abababca”进行匹配的过程之一）。
image
如图所示，当在主串的i处匹配失败，其之前长度为6的字符串“ababab”均已匹配成功。此时，由PMT表我们可知，子串“ababab”的value为4，即其四位前缀与四位后缀是一致的。又因为在主串中，i之前的四位与j之前的四位字符均一致。故，目标串的四位前缀与主串中i之前的四位字符一致。我们可以省略对该子串的比较，直接在目标串的j=4的位置与主串的当前位置i继续比较。
在上面是叙述中，我们发现，匹配失败，并不会导致主串索引i改变，只会影响目标串索引j出现变化。并且，有趣的是，以图中的过程为例，当j=6时，匹配失败，即最后一个成功匹配的j是5。之后j回溯的位置4正好是PMT表中index为5时的value值。根据这个原理，我们就可以跳过不需要的比较，只通过修改目标串索引的位置即可进行快速匹配。
image
那么，我们引入next表的目的是什么呢？由于在某一位置匹配失败时，都要查看其前一个位置对应的PMT值，故我们将PMT数据均偏移一位，直接对应于当前位置，以便在快速查找下一步时，可以直接得到目标串索引j的位置。因此，我们把PMT值偏移后的数据叫做next数据，为了补位，next的首位赋值为-1。
因此，有了next的方式，我们就可以对朴素匹配法进行优化了。
2.2 匹配过程
NSInteger KMPFindIndex(const char *sourceStr, const char *targetStr) {
// 获取目标串的next信息，以备匹配时进行回溯（KMP算法核心）
NSArray *nextInfo = getNextInfo(targetStr);
NSLog(@"next - %@", nextInfo);
// 获取两串长度
NSInteger sourceLength = strlen(sourceStr);
NSInteger targetLength = strlen(targetStr);
// 主串索引
NSInteger i = 0;
// 目标串索引
NSInteger j = 0;
// 均在范围内查找
while ((i < sourceLength)
&& (j < targetLength)) {
if ((j == -1)
|| (sourceStr[i] == targetStr[j])) {
// 字符匹配时，索引均后移，准备下一次匹配(j为-1即为了防止出现next[0] = -1的情况出现)
i += 1;
j += 1;
} else {
// 字符不匹配，i不变，j回溯为next中对应的位置，作为下次匹配的起点
j = [nextInfo[j] integerValue];
}
}
if (j == tragetLength) {
return i - j;
}
return NSNotFound;
}
2.3 生成Next数组的过程
我们知道，生成Next数据的过程，即在每一个位置上，获取前面子串里，前后缀集合中最长的公共子串的长度。
如目标字符串“ABCDABDE”，我们以k作为前缀索引，j为后缀索引。如下图，当在字符索引在“D”时（即j为6时），其子串“ABCDAB”的最长前后缀公共子串长度为2（子串“AB”的长度），故next[6] = 2。我们还可知，在j为5时，next[5] = 1，即在j = 5时，公共子串最大长度为1（子串“A”的长度）。故我们可以得到：在当前字符存在有效next值时（Pk == Pj时），下一个字符的next即为之前next位置的下一个，即next[j + 1] = next[j] + 1 = k + 1。
image
若Pk与Pj不相等，如图中k为2，j为6时。按照KMP的思想，后缀j不变，需要更新前缀k，以便找到另一个字符与Pj相同。故将前缀索引k修改为next[k]以继续进行比较（缩小前缀查找范围），直到找到相同的字符“D”或没有相同字符为止。
按照这个思想，生成next数据的实现为：
NSArray *getNextInfo(const char *targetStr) {
// 创建返回的next数组
NSMutableArray *nextInfo = [[NSMutableArray alloc] initWithCapacity:10];
nextInfo[0] = @(-1); // 人为指定首位的next值为-1（首位无法回溯，故此值只是占位用）
// 获取字符串长度
NSInteger strLength = strLen(targetStr);
NSInteger k = -1; // 前缀索引初始值
NSInteger j = 0; // 后缀索引初始值（后缀必须大于前缀才有效）
// 以后缀索引作为遍历范围（-1为了防止最后无效的自加1）
while (j < strLength - 1) {
if ((k == -1)
|| (targetStr[k] == targetStr[j])) {
// 前缀为初值索引时，无条件后移并记录（即没有有效前后缀公共串）
// 当前位置的字符相同，即找到了公共前后缀字符串，记录下一个位置的next值
// 下一位置的next值即为当前next的索引值k再加1
k += 1;
j += 1;
nextInfo[j] = @(k);
} else {
// 当前位置字符不同
// 按照KMP思想，j不回溯，k回溯为下一次的查找索引
k = [next[k] integerValue];
}
}
return [nextInfo copy];
}
Objective-C实现的代码地址：点击查看
2.4 Next数组的优化
我们设想一下这种情况：目标串为“abcabc”，主串为“abacababc”，其中一种比较情况如下图：
img
即此时，第四位比较失败（“c”与“b”不同）。我们知道，此时目标串下一次比较的索引j为next[j]，即第二位。也就是目标串右移j-next[j]位（2位）。
img
如图所示，由于移动后，第二位的字符仍然为“b”，显然比较失败。在这种情况下，本次比较实际上是没有意义的。那么应该如何避免这种比较呢？
其实，在正常情况下，当匹配失败时，我们还会进一步缩小匹配范围（j = next[j]），故在这种情况下（next[j]指向的字符与当前字符相同时），我们只需再次递归next[j]，跳过相同字符即可。
因此，解决办法就是，在生成next数组时，在当前Pk和Pj相同的情况下，若下一位的j与k指向的字符相同，直接设置该位置的next为next[k]即可：
NSArray *getNextInfo(const char *targetStr) {
NSMutableArray *nextInfo = [[NSMutableArray alloc] initWithCapacity:10];
nextInfo[0] = @(-1);
NSInteger strLength = strLen(targetStr);
NSInteger k = -1; // 前缀索引初始值
NSInteger j = 0; // 后缀索引初始值（后缀必须大于前缀才有效）
// 以后缀索引作为遍历范围
while (j < strLength - 1) {
if ((k == -1)
|| (targetStr[k] == targetStr[j])) {
// 前缀为初值索引时，无条件后移并记录（即没有有效前后缀公共串）
// 当前位置的字符相同，即找到了公共前后缀字符串，记录下一个位置的next值
k += 1;
j += 1;
// nextInfo[j] = @(k); // 修改
if (targetStr[k] == targetStr[j]) {
// 下一位的前后缀字符相同
nextInfo[j] = @(nextInfo[k]); // next跳过当前的前缀位置，直接指向前缀位置的next位置
} else {
// 下一位的前后缀字符不同（正常情况）
nextInfo[j] = @(k); // 原始匹配，next指向前缀后面的位置
}
} else {
// 当前位置字符不同
k = [next[k] integerValue];
}
}
return [nextInfo copy];
}
最终，优化后的next数组信息如下表所示（以目标串“abab”为例）：
img
使用优化后的next数组，可以再次减少一些不必要的比较。
2.5 时间复杂度
KMP方式的运算次数为计算next数组的次数与匹配主串的次数之和，即O(m + n)。
参考引用：
网友评论