Kotlin面试助手：字符串匹配技巧

【出自WR面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定主字符串s与模式字符串P，判断P是否是S的子串，如果是，则找出P在S中第一次出现的下标。

分析与解答：

对于字符串的匹配，最直接的方法就是挨个比较字符串中的字符，这种方法比较容易实现，但是效率也比较低。对于这种字符串匹配的问题，除了最常见的直接比较法外，经典的KMP算法也是不二选择，它能够显著提高运行效率，下面分别介绍这两种方法。

方法一：直接计算法

假定主串S=“S₀S₁S₂…S_m”，模式串P=“P₀P₁P₂P_n”。实现方法是：比较从主串S中以S_i（0＜=i＜m）为首的字符串和模式串P，判断P是否为S的前缀，如果是，那么P在S中第一次出现的位置则为i，否则接着比较从S_i+1开始的子串与模式串P，这种方法的时间复杂度为O（m*n）。此外如果i＞m-n的时候，在主串中以S_i为首的子串的长度必定小于模式串P的长度，因此，在这种情况下就没有必要再做比较了。实现代码如下：

程序的运行结果如下：

3

算法性能分析：

这种方法在最差的情况下需要对模式串P遍历m-n次（m、n分别为主串和模式串的长度），因此，算法的时间复杂度为O（n（m-n））。

方法二：KMP算法

在方法一中，如果“P₀P₁P₂…P_j-1”==“S_i-j…Si_-1”，模式串的前j个字符已经和主串中i-j到i-1的字符进行了比较，此时如果P_j！=S_i，那么模式串需要回退到0，主串需要回退到i-j+1的位置重新开始下一次比较。而在KMP算法中，如果P_j！=S_i，那么不需要回退，即i保持不动，j也不用清零，而是向右滑动模式串，用P_k和S_i继续匹配。这种方法的核心就是确定k的大小，显然，k的值越大越好。

如果P_j！=S_i，可以继续用P_k和S_i进行比较，那么必须满足：

（1）“P₀P₁P₂…P_k-1”==“S_i-kS_i-1”(www.xing528.com)

已经匹配的结果应满足下面的关系：

（2）“P_j-k…P_j-1”==“S_i-k…S_i-1”

由以上这两个公式可以得出如下结论：

“P₀P₁P₂…P_k-1”=“P_j-k…P_j-1”

因此，当模式串满足“P₀P₁P₂…P_k-1”==“P_j-k…P_j-1”时，如果主串第i个字符与模式串第j个字符匹配失败，只需要接着比较主串第i个字符与模式串第k个字符。

为了在任何字符匹配失败的时候都能找到对应k的值，这里给出next数组的定义，next[i]=m表示的意思为“p₀p₁p_m-1”=“p_i-m…p_i-2p_i-1”。计算方法如下：

（1）next[j]=-1（当j==0时）。

（2）next[j]=max（Max{k|1＜k＜j且“p₀…p_k”==“p_j-k-1…p_j-1”}）

（3）next[j]=0（其他情况）

实现代码如下：

程序的运行结果如下：

从运行结果可以看出，模式串P="abaabc"的next数组为{-1，0，0，1，1}，next[3]=1，说明P[0]==P[2]。当i=3、j=3的时候S[i]！=P[j]，此时主串S不需要回溯，跟模式串位置j=next[j]=next[3]=1的字符继续进行比较。因为此时S[i-1]一定与P[0]相等，所以就没有必要再比较了。

算法性能分析：

这种方法在求next数组的时候循环执行的次数为n（n为模式串的长度），在模式串与主串匹配的过程中循环执行的次数为m（m为主串的长度）。因此，算法的时间复杂度为O（m+n）。但是由于算法申请了额外的n个存储空间来存储next数组，因此，算法的空间复杂度为O（n）。