模式匹配

模式匹配

子串的定位操作通常称为串的模式匹配，本小节主要介绍简单的模式匹配算法、KMP算法、KMP算法的进一步优化。

简单的模式匹配算法

简单的模式匹配算法，通过暴力搜索。

int Index(string s, string t)
{
    int i = 0, j = 0;
    while(i<s.length() && j < t.length())
    {
        if(s.at(i) == t.at(j))
        {
            i++;
            j++;
        }
        else
        {
            i = i - j +1;
            j = 0;
        }
    }
    if (j >= t.length())
        return i - j;
    return -1;
};

KMP算法

在暴力匹配中，每趟匹配失败都是模式向后移一位再从头比较，这种频繁的重复使模式串不断地自我比较，因此其效率较低。

从分析模式本身的结构来看，若已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么此时已匹配相等的前缀序列的该后缀及其后面展开区域有可能匹配。

PM表

字符串的前缀、后缀和部分匹配值

• 前缀:除最后一个字符以外，字符串的所有头部子串。
• 后缀:除第一个字符以外，字符串的所有尾部子串。
• 部分匹配值:字符串的前缀和后缀的最长相等前后缀长度。

以'ababa'为例五，'ababa'的部分匹配值为00123：

• 'a'的前缀和后缀为空集，最长相等前后缀长度为0;
• 'ab'的前缀为$\{a\}$，后缀为$\{b\}$，$\{a\}{\cap}\{b\}=\varnothing$，最长相等前后缀长度为0;
• 'aba'的前缀为$\{a,ab\}$，后缀为$\{ba,a\}$，$\{a,ab\}{\cap}\{ba,a\}=\{a\}$，最长相等前后缀长度为1;
• 'abab'的前缀为$\{a,ab,aba\}$，后缀为$\{bab,ab,b\}$，$\{a,ab,aba\}{\cap}\{bab,ab,b\}=\{ab\}$，最长相等前后缀长度为2;
• 'ababa'的前缀为$\{a,ab,aba,abab\}$，后缀为$\{baba,aba,ba,a\}$，$\{a,ab,aba,abab\}{\cap}\{baba,aba,ba,a\}=\{a,aba\}$，最长相等前后缀长度为3;

'ababa'对应的PM(Partial Match)(部分匹配值)表格如下:

编号	1	2	3	4	5
S	a	b	c	a	c
PM	0	0	0	1	0

使用PM表进行字符串匹配:

• 第一趟匹配过程

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串	a	b	c

由于'c'和'a'不匹配，前面的2个字符'ab'是匹配的，通过查表可知，最后一个匹配字符'b'对应的部分匹配值为0，因此按照下述公式，计算子串需要向后移动的位数:

$$\text{移动位数=已匹配的字符数-对应的部分匹配值}$$

因此$2-0=0$，故将子串向右移动$2$位。

• 第二趟匹配过程

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串			a	b	c	a	c

'c'和'b'不匹配，查看最后一个字符'a'的部分匹配值为$1$，因此$4-1=3$，将子串右移$3$位。

• 第三趟匹配过程

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串						a	b	c	a	c

全部匹配成功，由于匹配过程中，主串没有回退，因此时间复杂度为$O(m+n)$.

KMP算法原理

如下图，当'c'与'b'不匹配时，此时匹配的前缀为'abca'，此时'abca'的最长公共元素为'a'，因此可以将子串直接移动$\text{移动位数=已匹配的字符数-对应的部分匹配值}$位，即$3$位。

主串	a	b	a	b	c	a	b	c	a	c	b	a	b
子串			a	b	c	a	c
子串				a	b	c	a	c
子串					a	b	c	a	c
子串						a	b	c	a	c

对公式$\text{移动位数=已匹配的字符数-对应的部分匹配值}$解释:

部分匹配值为最长公共匹配前后缀，因此用已经匹配的字符数-对应的部分匹配值，可以使最长的前缀挪到相应的后缀上。

对算法的改进
在使用部分匹配，每当失败时，就要去搜索他前面一个元素的匹配值，使用起来不方便，因此将PM表向右移动一位，此时，只需找匹配失败元素对应的值即可。

编号	1	2	3	4	5
S	a	b	c	a	c
next	-1	0	0	0	1

• 第一个元素右移缺失后使用$-1$来填充，因为第一个元素就匹配失败的话，只需将子串向后移动一位，不需要计算移动位数。

• 最后一个元素在右移过程中溢出，由于最后一个元素没有后继元素需要使用他的部分匹配值，因此可以舍去。

此时推导出的子串移动位数(Move)公式为:

$$\text{Move}=(j-1)-\text{next[j]}$$

相当于将子串的指针$j$回退到

$$j = j-\text{Move}=j-((j-1)-\text{next}[j])=\text{next}[j]+1$$

next数组

$\textbf{next}$的含义: 在子串的第$j$个字符与主串发生失配时，跳到子串 $\text{next}[j]$位置重新与主串当前位置进行比较。

$\textbf{next}$公式如下:

$$\textbf{next}[j]=\left\{ \begin{array}{l} 0,\ j=1\\ max\{k|1<k<j,\text{且}p_{1}{\cdots}p_{k-1}=p_{j-k+1}{\cdots}p_{k-1}\text{,当此集合不为空时}\}\\ 1,\text{其他情况} \end{array} \right.$$

使用计算机对$\textbf{next}$数组求解:

• 1. 由公式有$\textbf{next}[1]=0$.
• 2. 若$\textbf{next}[j]=k$，则:

• 2.1 若$\text{p}_k=\text{p}_j$，则表明在模式串$\text{p}_1...\text{p}_{k-1}\text{p}_k=\text{p}_{j-k+1}...\text{p}_{j-1}\text{p}_j$中不可能出现$k^{'}>k$满足上述条件，此时$\textbf{next}[j+1]=\textbf{next}[j]+1$.

• 2.2 若$\text{p}_k{\neq}\text{p}_j$，则表明在模式串中$\text{p}_1...\text{p}_{k-1}\text{p}_k{\neq}\text{p}_{j-k+1}...\text{p}_{j-1}\text{p}_j$，此时将$k$滑动到$\textbf{next}[k]$，即令$k=\textbf{next}[k]$，若$\text{p}_k{\neq}\text{p}_j$，则以此类推，直到找到更小的$k^{'}$使$k^{'}=\textbf{next}[\textbf{next...[k]}](1<k^{'}<k<j>>)$，满足条件$\text{p}_1...\text{p}_{k-1}\text{p}_{k^{'}}=\text{p}_{j-k^{'}+1}...\text{p}_{j-1}\text{p}_j$，则$\textbf{next}[j+1]=k^{'}+1$.

• 3. 当不存2.中的$k^{'}$满足上述条件时，即不存在长度更短的相等前缀后缀时，令$\textbf{next}[j+1]=1$

KMP算法流程举例

设S='aabaabaabaac'，P='aabaac'，求P的$\textbf{next}$及KMP匹配过程。

使用手工法求$\textbf{next}$数组，步骤如下:

1. 求PM表

j	1	2	3	4	5	6
P	a	a	b	a	a	c
PM	0	1	0	1	2	0

2. 将PM表向右移动一位

j	1	2	3	4	5	6
P	a	a	b	a	a	c
PM Moved	-1	0	1	0	1	2

3. 将PM Moved所有元素加1

j	1	2	3	4	5	6
P	a	a	b	a	a	c
next	0	1	2	1	2	3

KMP匹配的过程如下:

匹配过程中进行的单个字符之间的比较次数为6+4+4

1. i=6，j=6时匹配失败，将P位于$\textbf{next}[j]$的数组移到j处。

j	1	2	3	4	5	6	7	8	9	10	11	12
S	a	a	b	a	a	b	a	a	b	a	a	c
P	a	a	b	a	a	c
next	0	1	2	1	2	3

2. i=9，j=6时匹配失败，将P位于$\textbf{next}[j]$的数组移到j处。

j	1	2	3	4	5	6	7	8	9	10	11	12
S	a	a	b	a	a	b	a	a	b	a	a	c
P				a	a	b	a	a	c
next				0	1	2	1	2	3

3. 匹配成功。

j	1	2	3	4	5	6	7	8	9	10	11	12
S	a	a	b	a	a	b	a	a	b	a	a	c
P							a	a	b	a	a	c
next							0	1	2	1	2	3

KMP的代码实现

采用先求解移位后的PM表，再对所有元素+1的方式实现。

vector<int> get_next(string P) {
    vector<int> next(P.length(), 0);
    next[0] = -1;
    int j = 0, k = -1;
    while (j < P.length()) {
        if (k == -1 || P.at(j) == P.at(k)) {
            k++;
            j++;
            next[j] = k;
        } else
            k = next[k];
    }
    for (int i = 0; i < P.length(); i++)
        next.at(i)++;
    return next;
}

KMP算法的改进-nextval数组

KMP缺陷

前面KMP定义的$\textbf{next}$数组在某些情况下存在缺陷，如下表所示。

主串	a	a	a	b	a	a	a	a	b
模式	a	a	a	a	b
j	1	2	3	4	5
next	0	1	2	3	4
nextval	0	0	0	0	4

使用KMP匹配的过程如下:

1. 第一次匹配

主串	a	a	a	b	a	a	a	a	b
模式	a	a	a	a
j	1	2	3	4
next	0	1	2	3

2. 第二次匹配

主串	a	a	a	b	a	a	a	a	b
模式		a	a	a
j		1	2	3
next		0	1	2

3. 第三次匹配

主串	a	a	a	b	a	a	a	a	b
模式			a	a
j			1	2
next			0	1

4. 第四次匹配

主串	a	a	a	b	a	a	a	a	b
模式				a
j				1
next				0

5. 第五次匹配

主串	a	a	a	b	a	a	a	a	b
模式					a	a	a	a	b
j					1	2	3	4	5
next					0	1	2	3	4

可以发现，该算法效率低下的主要的原因在于 $\text{P}_{\textbf{next}[j]} = \text{P}_{j}$， 上述例子中$\text{P}_{\textbf{next}[4]=3}=P_{4}=a$、$\text{P}_{\textbf{next}[3]=2}=P_{3}=a$、$\text{P}_{\textbf{next}[2]=1}=P_{2}=a$， 因此后三次使用相同的字符和$\text{S}_{4}$匹配，因此无意义，一定失配。

KMP改进

出现上述问题后，遇到$\text{P}_{\textbf{next}[j]} = \text{P}_{j}$的处理方法:
若出现上述情况，则将$\textbf{next}[\textbf{j}]$修改为$\textbf{next[\textbf{next}[\text{j}]]}$，直至两者不再相等。