首页 > 代码库 > [考研系列之数据结构]线性表之字符串

[考研系列之数据结构]线性表之字符串

基本概念


串(字符串) 由0个或多个字符组成的有限序列,例如s="hello world"
串名 上例中的s
子串 某串任意连续字符组成的子序列,称为此字符串的子串
空串 0个字符的串,s=""
空格串 由一个或多个字符组成的串

模式匹配算法

作用定位某子串T在字符串S中的位置
主串S
模式串 T
 
针对模式匹配算法从简到难我们需要了解两种算法:

[1] 朴素的模式匹配算法
[2] KMP匹配算法

朴素的模式匹配算法:

所谓朴素就是简单,这是一种简单的模式匹配。让我们从一个栗子来看朴素的模式匹配算法是如何进行的。
主串S="ababcabcacbab"
模式串T="abcac"

直接截图严书了。



对于朴素的模式匹配算法,我们依次将T的第j个字符和S的第i个字符比较,如果

T[i]==S[j]匹配成功 ++i;++j;进行下一个字符的匹配
T[i]!=S[j] 
匹配失败
T需要重新从第0个字符开始匹配
S的j也需要回溯到某个位置

这里关键是j应该回退到那个位置。


上面的草图画出了S和T在某个位置匹配失败了,那么i需要退回到0而j应该退回到x+1;通过很简单的计算
j-x=i
x+1=j-i+1

下面,什么时候算法结束?
当T或者S已经匹配了最后一个字符的时候,程序结束。当T匹配到最后一个字符且仍然匹配成功那么整个匹配就是成功的,反之失败。
下面给出C++风格的代码:
int index(String S,String T)
{
    int i=0;
    int j=0;
    while(i<T.length&&j<S.length)
    {
        if(T[i]==S[j]) //本次字符匹配成功
        {
            ++i;++j;
        }
        else //本次字符匹配失败
        {
            j=j-i+1;i=0;
        }
    }
    if(i==T.length) //成功匹配
        return j-i;
    return 0;
}

KMP匹配算法

对于朴素的匹配算法,在最差的情况下,它只能取得O(S.length*T.length)的算法复杂度,而基于朴素模式匹配算法的KMP能在O(T.length+S.length)内完成。
让我们先想想,朴素的匹配算法最耗时的操作是什么?
是j的回溯,j需要回溯到j-i+1的位置进行下一轮匹配。那么如何能减少j的回溯长度呢?依然以朴素匹配算法中的实例为栗子。


我们看到T匹配到"abca"时,匹配失败,如果按照朴素匹配算法,下面S会跳到"bcbb..."的第二个位置进行匹配,但是很明显,第一次就会匹配失败,第三次"cbb..."依然会在第一次匹配的时候失败,那么这两轮匹配其实是没有意义的,因为从模式串T看来,由于是在第四个位置匹配失败的,但是它前面的三个位置是匹配成功的,它知道下一轮匹配的S的首字符是T[1]="b",再下次是T[2]="C"。那么,我们通过研究T的规律是可以减少回溯减少不必要的匹配轮数的。
下面正式进入KMP算法。首先来一段理论的说明:

KMP匹配算法主要步骤有两步
[1] 求next数组
[2] 利用next数组进行匹配

下面首先让我们看看next数组
含义:next[j]表示当T[j]和S[i]失配的时候,在T中需要和S[i]重新比较的字符的位置,也就是会比较T[next[j]]和S[i]的关系
定义:


[待续]