# 🔰模式匹配

给定主串 S = "S1S2...Sn"和模式 T = ”t1t2...tn“ ,在S中寻找T的过程称模式匹配。如果匹配成功,返回T在S中的位置,如果匹配失败返回0.

假设串采用顺序存储结构,串的长度放在数组0号单元,串值从1号单元开始存放:

模式匹配问题的特点:

1、 算法的一次执行时间不容忽视:问题规模通常很大,常常需要在大量信息中进行匹配 2、 算法改进所得的积累效益不容忽视:模式匹配操作经常被调用,执行频率高。

🔸介绍两种匹配方法: 1️⃣: BF算法 2️⃣: KMP算法

# 1️⃣模式匹配—BF算法

基本思想🖌:

📝从主串的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;否则,从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,直到T中的字符全部比较完毕,则说明本趟匹配成功; 或S中字符全比较完,则说明匹配失败。

算法过程🖌:
STEP1: 在串S和串T中设比较的起始下标i和j;
STEP2: 循环直到S或T的所有字符均比较完;

  • 2.1 如果S[i]==T[j],继续比较S和T的下一个字符;
  • 2.2 否则,将i和j回溯,准备下一趟比较;
    STEP3: 如果T中所的字符都比较完,则匹配成功,返回匹配的起始比较下标:否则,匹配失败,返回0;

算法步骤🖌:
入口函数(主串、模式串、起始位置)

  1. 两个变量,一个是主串下标i,一个是子串下标j
  2. 在两下串中比较:如果相同,下标下移,否则退回

算法描述🖌:

int Index_BF (SString S, SString T, int pos){
    i = pos, j = 1;
    while (i <= S[0] && j <= T[0]){
        if (S[i] == T[j]){ 
            i++; 
            j++;
        } else {
            i = i - j + 2; 
            j = 1;
        }
    }
    if (i > T[0]){
        return i-T[0];
    } else {
        return 0; 
    }
}

算法性能🖌:
设串S长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况:
👉情况1️⃣:最好情况,即不成功匹配都发生在串T的第1个字符。
设匹配成功发生在Si处,则i-1次不成功的匹配中共比较i-1次,第i次成功匹配,共比较m次,把以共花i-1+m次,所有匹配成功的可能情况共为n-m+1种,则时间复O(m + n)
👉情况2️⃣:最坏情况,不成功匹配都发生在串T的最后一个字符串
前i-1次,每次比较m次才确定失配,前i-1次共比较(i-1)*m次,总共比较(i-1)m + m次,刚时间复杂度为O(mn)

# 2️⃣模式匹配—KMP算法

KMP算法思想🖌
本算法是对BF算法思想的改进,每趟匹配过程中出现字符比较不等时,不回溯主指针i,利用已得到的”部分匹配“结果将模式串向右滑尽可能远的一段距离,继续进行比较。
定义next[j]函数,表明当前模式中第j个字符与主串中相应字符”失配“时,在模式串中需要重新和主串中该字符进行比较的字符位置。

  1. 小结1️⃣: next[j]函数的意义
    next[j]函数表征着模式串p中最大的相同首字串和尾子串(真子串)的长度。可见模式串中相似部分越多,则next[j]函数越大,它既表示模式串中的字符之间的相关度越高,模式串向右滑动的越远,与主串进行比较的次数越少,时间复杂度越低。
  2. 小结2️⃣: 回溯模式串也就是子串
    第一,主串中的i可以不回溯,模式串向右滑动到新的比较起点k,并且k仅与模式串p(模式串)T有关。 第二,注意两个问题,
    问题1:如何由当前部分匹配结果,确定模式串向右滑动的新比较起点K?
    问题2:模式串应该向右滑动多远才是最高效率的?
  3. 计算next[j]的方法
    🔖情形1:
    当j=1时,next[j]=0;
    next[j]=0表示不进行字符串比较
    🔖情形2:
    当j>1时,next[j]的值为:
    模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度为1。
    🔖情形3:
    若无首尾相同的子串next[j]的值为1。
    next[j]=1表示模式串从头部开始比较

KMP算法描述🖌

int index_KMP(SString S, SString T, int pos){
    i = pos,j = 1;
    while (i <= S[0] && j <= T[0]){
        if( j== 0 || S[i] == T[j]){
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if( j > T[0]){
        return i-T[0];
    } else {
        return 0;
    }
}

void get_next(SString T, int &next[]){
    i = 1;
    next[1] = 0; j = 0 ;
    while( i < T[0]){
        if (j == 0 || T[i] == T[j]){
            ++i; 
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

KMP算法练习🖌:
设目标子串 S="aaabaaaab" 模式串T=“aaaab”,S的长度n=9,T的长度m=5。用指针i表示目标串S的当前比较字符位置,用j表示模式串T的当前比较位置,KMP比较过程如下

j 1 2 3 4 5
T[j]模式 a a a a b
next[j] 0 1 2 3 4

在主串S="aaabaaaab"模式串T=“aaab”匹配时,当i=4,j=4时,S.data[4]<>T.data[4],此是next[j]还需进行i=4、j=3,i=4、j=2,i=4、j=1,这样三次比较我们会发现,模式串中前4个字符是相等的,因些不需要和主串的第四个字符进行比较,直接进行i=5、j=1时的字符比较。因此可以如下图

j 1 2 3 4 5
T[j]模式 a a a a b
next[j]=k 0 1 2 3 4
nextVal[j] 0 0 0 0 4

小结:比较T.data[j]和T.data[k],若不等,则nextVal[j]=next[j],若相等,nextVal[j]=nextVal[k]

KMP算法的时间复杂度🖌
设主串S长度为n,模式串T长度为m,在KMP算法中next数组的时间复杂度为O(m),在后面的匹配中因S的下标不减所以不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(m+n)