《大话数据结构》之串

2019-03-17

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”为例，其匹配表如下：

其中，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”进行匹配的过程之一）。

如图所示，当在主串的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值。根据这个原理，我们就可以跳过不需要的比较，只通过修改目标串索引的位置即可进行快速匹配。

那么，我们引入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。

若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”，其中一种比较情况如下图：

即此时，第四位比较失败（“c”与“b”不同）。我们知道，此时目标串下一次比较的索引j为next[j]，即第二位。也就是目标串右移j-next[j]位（2位）。

如图所示，由于移动后，第二位的字符仍然为“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”为例）：

使用优化后的next数组，可以再次减少一些不必要的比较。

2.5 时间复杂度

KMP方式的运算次数为计算next数组的次数与匹配主串的次数之和，即O(m + n)。

参考引用：

如何更好的理解和掌握 KMP 算法?

很详尽KMP算法（厉害）