首页 理论教育 Kotlin面试助手:字符串匹配技巧

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

时间:2023-10-31 理论教育 版权反馈
【摘要】:对于这种字符串匹配的问题,除了最常见的直接比较法外,经典的KMP算法也是不二选择,它能够显著提高运行效率,下面分别介绍这两种方法。方法二:KMP算法在方法一中,如果“P0P1P2…Pj-1”==“Si-j…Si-1”,模式串的前j个字符已经和主串中i-j到i-1的字符进行了比较,此时如果Pj!

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

【出自WR面试题】

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

题目描述:

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

分析与解答:

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

方法一:直接计算法

假定主串S=“S0S1S2…Sm”,模式串P=“P0P1P2978-7-111-61212-4-Part02-261.jpgPn”。实现方法是:比较从主串S中以Si(0<=i<m)为首的字符串和模式串P,判断P是否为S的前缀,如果是,那么P在S中第一次出现的位置则为i,否则接着比较从Si+1开始的子串与模式串P,这种方法的时间复杂度为O(m*n)。此外如果i>m-n的时候,在主串中以Si为首的子串的长度必定小于模式串P的长度,因此,在这种情况下就没有必要再做比较了。实现代码如下:

程序的运行结果如下:

3

算法性能分析

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

方法二:KMP算法

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

如果Pj!=Si,可以继续用Pk和Si进行比较,那么必须满足:

(1)“P0P1P2…Pk-1”==“Si-k978-7-111-61212-4-Part02-264.jpgSi-1”(www.xing528.com)

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

(2)“Pj-k…Pj-1”==“Si-k…Si-1

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

“P0P1P2…Pk-1”=“Pj-k…Pj-1

因此,当模式串满足“P0P1P2…Pk-1”==“Pj-k…Pj-1”时,如果主串第i个字符与模式串第j个字符匹配失败,只需要接着比较主串第i个字符与模式串第k个字符。

为了在任何字符匹配失败的时候都能找到对应k的值,这里给出next数组的定义,next[i]=m表示的意思为“p0p1978-7-111-61212-4-Part02-265.jpgpm-1”=“pi-m…pi-2pi-1”。计算方法如下:

(1)next[j]=-1(当j==0时)。

(2)next[j]=max(Max{k|1<k<j且“p0…pk”==“pj-k-1…pj-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)。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈