字符串模式匹配的两大经典算法。
概念：
主串，又称目标串
子串，又称模式串
模式匹配就是在主串中匹配模式串。

KMP算法

模式串的next数组求法：

1. next数组下标从1开始
2. next[j] 值为模式串前j-1个字符最长相等前后缀长度+1
3. next[1]=0
4. 串本身不能作为前后缀
5. 模式匹配失败时，next数组规定了模式串向后滑动的位数

例题：
P='aabaac'
next={0,1,2,1,2,3}

KMP算法改进

假设\(T[i]≠P[j]\)导致失配 。若\(P[j]==P[next[j]]\)，此时模式串移动\(next[j]\)必然也会失配，改进用nextval数组代替next数组：

nextval[1]=0;
for(j>1;j<=n;j++)
    if(P[j]==P[next[j]]) 
        nextval[j]=nextval[next[j]];
    if(P[j]≠P[next[j]]) 
        nextval[j]=next[j];

BM算法

基本思想

设目标串T，模式串为P

1. 对于模式串P，计算\(CharJump[x]\)和\(MatchJump[k]\),即坏字符和好后缀；

2. 将T与P的第一个字符对齐。T与P从右向左的逐字符比较，直至找到一个不匹配字符或者P中所有字符都匹配成功；

3. 若出现失配，即存在\(T[i]≠P[k]\)，此时坏字符\(x=T[i]\)，好后缀\(P'=P[(k+1) … (len(P)-1)]\)
   按如下规则计算目标串T中查找指针向右移动的距离\(dist[i]\)：

   • 若此时T与P已有部分字符匹配（即存在“好后缀” ）

     \(dist[i]=max(CharJump[x], MatchJump[k])\)

   • 若不存在“好后缀”,即最后一个字符就失配

     \(dist[i] =CharJump[x]\)

4. 若\((i+dist[i])≤Len(T)-1\)，则移动模式字符串P，使之与\(T[i+dist[i]]\)右对齐，重复Step2；否则，认为T中不存在与P匹配的子串，返回匹配失败。

CharJump[x]计算

• 若字符x在P中出现，假设\(p[j]==x\)，则\(CharJump[x]=Len(P)-max(j)-1\) 即最靠后的字符x到模式串尾的字符个数；
• 否则，\(CharJump[x]=Len(P)\)；

例题：

若模式串为"abcadb"，则

• CharJump['a']=2
• CharJump['b']=0
• CharJump['c']=3
• CharJump['d']=1
• CharJump[all others]=6

MatchJump[k]计算

T中查找指针的移动距离dist=模式串P的移动距离shift+好后缀的长度

1. MatchJump数组初始化

   \(MatchJump[k]=Len(P)-k-1+Len(P)\)
   \(MatchJump[Len(P)-1] = 1\)

   其中\(k∈[0,Len(P)-2]\)
   即模式串中字符到模式串尾距离+模式串长度

2. 若存在好后缀，则依据“好后缀规则 ”，重新调整\(MatchJump[k]（k∈[0,Len(P)-2]）\) （假定：好后缀P’为P[k+1]…P[Len(p)-1] ）

   • 若好后缀P’在P中存在重复模式，且重复模式的前一个字符 P[k] 与 P[t] 不等，即P[t +1]…P[Len(p)-1-k+t ]== P[k+1]…P[Len(P)-1]且P[t]≠P[k]，
     则\(MatchJump(k)=[Len(P)-1-k]+min(k-t)\)
     即P[t]到模式串尾部的距离
   • 若不满足上述规则，且P的前缀为好后缀P’中的某个子后缀P"的重复模式，即(P"=P[t] … P[Len(p)-1]==P[0] … P[Len(p)-1-t]) (t>k+1)，则MatchJump(k)=[Len(P)-1-k]+min(t)

例1：

例2：

例3：