KMP算法

写在前面的话

看了眼第一次写这篇文章的时间,是4/12,现在已经是7/1了,还没发表,也是够尴尬了吧,很多事情,就是这样,一旦你拖了下去,就再没有继续的时候,迄今为止,其实这篇文章依旧尚未终结,我还差了一个具体事例讲解,先发表出来挖个坑吧,等到考完试填了。

7/18:更新…

正文

定义

子串的定位运算通常称为串的模式匹配/串匹配。著名的模式匹配算法是BF算法KMP算法

BF算法

步骤

  • 分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置,i初值为pos,j初值为1。

  • 如果两个串均未比较到串尾,即i和j分别小于等于S和T的长度时,则循环执行以下操作:

  1. S.ch[i]和T.ch[j]比较,若相等,则i和j分别指示串中下个位置,继续比较后续字符。
  2. 若不等,指针后退重新开始匹配,从主串的下一个字符(i-j+2)起再重新和模式的第一个字符(j=1)比较。
  • 如果j>T.length,说明模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则匹配成功,返回和模式T中第一个字符相等的字符在主串S中的序号(i-T.length);否则称匹配不成功,返回0。

源代码表示

1
2
3
4
5
6
7
8
9
10
11
12
int Index(SString S, SString T, int pos)
{
int i=pos,j=1;
while (i<=S.length && j<=T.length)
{
if (S.ch[i]==T.ch[j])
{++i;++j;}
else {i=i-j+2;j=1;}
}
if (j>T.length) return i-T.length;
else return 0;
}

KMP算法

改进之处

每当一趟匹配过程中出现字符比较不相等时,不需回溯i指针,而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后,继续进行比较。

假设主串为$ s_1s_2{\cdots}s_n $,模式串为$ p_1p_2{\cdots}p_m $

问题

当主串中第i个字符与模式串中第j个字符“失配”时,主串中的第i个字符应与模式串中哪个字符进行比较?

假设此时应与模式中第k(k < j)个字符继续比较,则须满足关系式:
$$
p_1p_2{\cdots}p_{k-1} = s_{i-k+1}s_{i-k+2}{\cdots}s_{i-1}\\
已得到的结果:\\
p_{j-k+1}p_{j-k+2}{\cdots}p_{j-1} = s_{i-k+1}s_{i-k+2}{\cdots}s_{i-1}\\
可以推出,须满足:\\
p_1p_2{\cdots}p_{k-1} = p_{j-k+1}p_{j-k+2}{\cdots}p_{j-1}
$$
其中关联如图所示:

若令$ next[j]=k $,则next[j]表明当模式串中第j个字符与主串中相应字符“失配”时,在该模式串中需要重新和主串中该字符进行比较的字符的位置。

模式串中的next函数

$$
next[j]=
\begin{cases}
0,j=1 & \text{($p_1$与$s_i$比较不等时,下一步进行$p_i$和$s_{i+1}$的比较)} \\
Max[k|1<k<j] & \text{(满足
$ p_1p_2{\cdots}p_{k-1}=p_{j-k+1}p_{j-k+2}{\cdots}p_{j-1} $ 的最大k值)}\\
1,k=1 & \text{(不存在相同子串,下一步进行$p_1$和$s_i$的比较)}
\end{cases}
$$

如何求next函数值

  • $ next[1]=0 $; 表明主串从下一字符$s_{i+1}$起和模式串重新开始匹配。 $ i=i+1;j=1 $ ;
  • 设$ next[j]=k $, 则$ next[j+1]=? $

a: 若$ p_k=p_j $,则有
$$
p_1p_2{\cdots}p_{k-1}p_k = p_{j-k+1}p_{j-k+2}{\cdots}p_{j-1}p_j
$$
说明$ next[j+1]=k+1=next[j]+1 $。

b: 若$ p_k{\neq}p_j $,可把求next值问题看成是一个模式匹配问题,整个模式串既是主串,又是子串。则需往前回溯,检查是否$ p_j=p_{next[k]} $,

若相等,则$ next[j+1]=next[k]+1 $;

若不等,检查是否$ p_j=p_{next[next[k]]} $,直到$ next[j+1]=1 $为止。

源代码表示

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
int Index_KMP(SString S,SString T, int pos)
{
i=pos,j=1;
while (i<=S.length && j<=T.length)
{
if (j==0 || S.ch[i]==T.ch[j])
{++i;++j;}
else j=next[j]; //模式串向右移动
}
if (j>T.length) return i-T.length;
else return 0;
}

计算next函数值

1
2
3
4
5
6
7
8
9
10
void get_next(SString T, int next[])
{//求模式串T的next函数值并存入数组next
i=1;next[1]=0;j=0;
while (i<T.length)
{
if (j==0 || T.ch[i]==T.ch[j])
{++i;++j;next[i]=j;}
else j=next[j];
}
}

实例分析

求串′ababaaababaa′的next数组:

先给出答案:

j 1 2 3 4 5 6 7 8 9 10 11 12
模式串 a b a b a a a b a b a a
Next[j] 0 1 1 2 3 4 2 2 3 4 5 6

计算过程:

next数组值的计算依据下面的分段函数

$$
next[j]=
\begin{cases}
0,j=1 & \text{($p_1$与$s_i$比较不等时,下一步进行$p_i$和$s_{i+1}$的比较)} \\
Max[k|1<k<j] & \text{(满足
$ p_1p_2{\cdots}p_{k-1}=p_{j-k+1}p_{j-k+2}{\cdots}p_{j-1} $ 的最大k值)}\\
1,k=1 & \text{(不存在相同子串,下一步进行$p_1$和$s_i$的比较)}
\end{cases}
$$

最大k值代表当模式中第j个字符与主串中第i个字符“失配”时,在该模式串中需要重新和主串中第i个字符进行比较的字符位置,最大k值与最终求得的next[j]值是相等的

一定要注意观察分段函数第二段求max[k]时的满足条件,模式串中的最大相同子串应该满足:

$$
p_1p_2{\cdots}p_{k-1}=p_{j-k+1}p_{j-k+2}{\cdots}p_{j-1}
$$

所以k值很关键,要找到一个最大k值,满足上式。

它是根据下面这张图片推出来的,假设主串为$s_1s_2···s_n$,模式串为$p_1p_2···p_m$,此时图片中对应的情形是主串中第i个字符与模式中第j个字符“失配”

下面结合这道题具体分析:

j 模式串 对应分段函数 最大相同子串数 最大k值 对应子串 next[j]
1 a 第一段 X X X 0
2 b 第三段 0 1 X 1
3 a 第三段 0 1 X 1
4 b 第二段 1 2 $ p_1=p_3 $ 2
5 a 第二段 2 3 $ p_1p_2=p_2p_3 $ 3
6 a 第二段 3 4 $ p_1p_2p_3=p_3p_4p_5 $ 4
7 a 第二段 1 2 $ p_1=p_6 $ 2
8 b 第二段 1 2 $ p_1=p_7 $ 2
9 a 第二段 2 3 $ p_1p_2=P_7p_8 $ 3
10 b 第二段 3 4 $ p_1p_2p_3=p_7p_8p_9 $ 4
11 a 第二段 4 5 $ p_1p_2p_3p_4=p_7p_8p_9p_{10} $ 5
12 a 第二段 5 6 $ p_1p_2p_3p_4p_5=p_7p_8p_9p_{10}p_{11} $ 6

写在后面的话

从这篇文章中可以看出来,里面的一些公式在hexo没有成功渲染出来,从网上查了下,好像是Markdown自带的 mathjax与hexo的公式渲染会有冲突,一些关键地方我先用图片代替了,先在这挖个坑,日后去解决这个问题…

8/3:补坑,把上面提到的这个问题解决了,也将图片又还原成公式了,这次没有问题,具体解决方法在这里:
hexo博客MathJax公式渲染问题

-------------The End-------------