模式匹配算法

KMP 算法

概述

在 s1 中寻找 s2，暴力算法在遇到字符不匹配的时候会令 s2 回溯到起点，s1 回溯到起点后面一格

A B C A B C D H
A B C E

这里发生失配，然后 j（s2 的元素指针）回溯到 0，i（s1 的元素指针）回溯到 1

A B C A B C D H
A B C E

显然这种回溯方式做了许多多余比较，KMP做法则是根据next数组做回溯

C B C A B C D H
C B C E

发生失配后，j 从 3 回溯到 1

C B C A B C D H
C B C E

前置知识

前后缀

字符串的前缀是从以第一个字符开始，任意元素结尾（除了字符串末尾元素外）组成的字符串的子字符串，字符串的后缀是以最后一个字符为结尾，任意字符（除了字符串起始元素外）开始的子字符串，相等的前缀和后缀的最大长度为最大相等前后缀长度，如果原字符串只有 1 个字符，最大相等前后缀长度视作 0

求 next 数组

从上面的表格可以看出，假如 s2 从 i 号跳转到 j 号，必须保证从 j 向前到开头的这一部分和从 i 向前相同长度的这一部分是完全相同的，也就是说 i 前面的一段字符串的最长相等前后缀的前缀的末尾的后面一位就是 j，由前缀的性质可知，j 同时也表示 i 之前的字符串的最大相等前后缀长度

1
2
3
4
5
6
7
8
9
10
11
12
13
int i = 0, j = -1;
next[0] = -1;
while(i<s2.length()-1)
{
	if(j==-1 || s2[i]==s2[j]) //i之前最大相等前后缀长为0，那么j就会为-1
	{
		i++,j++; //相当于是对进入循环的i+1的回溯数组赋值，所以i只需要遍历到小于s2.length()-1
		next[i] = j;
	}
	else
		j = next[j];
		//相当于是用j向前一直到起点的字符串来匹配i向前等长的字符串，匹配失败就回溯
}

Kmp 主程序

求出 next 数组之后只需要将 s2 与 s1 逐个字符匹配，如果失配，就让 s2 按照 next 数组回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//返回第一次匹配成功的起点
int i = 0,j = 0;
	while(i<s1.length())
	{
		if( j==-1 || s1[i]==s2[j])  //s2中没有元素可以匹配到s1[i]那么j就会为-1
		{
			i++,j++;
			if(j==s2.length())
				break;
		}
		else
			j = next[j];
	}
	if(j==s2.length())
		return i - j ;
	else
		return -1;

瑕疵与优化

考虑 s1 == “aaaaaaaabaaaaac” s2 == “aaaaac”的情况，c 失配后回溯到 4 号 a，又失配，回溯到 3 号 a，然后回溯到 2 号 a…. 一直到 0 号 a 失配，回溯到-1，同一个字符失配过一次后就不需要再尝试匹配，在求 next 的过程中，加入判断语句，判断失配元素与其回溯元素是否相等，若相等，就将回溯元素的回溯元素传递给失配元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int i = 0, j = -1;
	next[0] = -1;
	while(i<s2.length()-1)
	{
		if(j==-1 || s2[i]==s2[j])
		{
			i++,j++;
			if(s2[i]!=s2[j])
				next[i] = j;
			else
				next[i] = next[j];
		}
		else
			j = next[j];
	}

AC 自动机

概述

字典树与 KMP 的结合，用于模式串过多，字典树运行时间过长的情况

代码逻辑

  • AC 自动机下标 0 为特意设定的头结点
  • 回溯数组的求法：让每个模式串的首字母回溯到 0，每一个结点 x 都回溯到与其存储相同字母的结点 bk，bk 父结点为 x 父结点的回溯结点，因为回溯的结点要么是 0 结点，要么是和自己存储相同字母的结点，所以从 bk 走到 0 的字符串必然和 x 走到 0 过程中经历相同长度的字符串的内容相同

核心代码_自动机结构体

1
2
3
4
5
6
struct node
{
    int bk; //回溯结点
    int cae;  //以此结点为终点的单词个数
    int letter[26]; //起始结点为当下结点，下标表示两结点之间对应的字母，值表示终止结点
}AC[maxn];

核心代码_建立字典树

1
2
3
4
5
6
7
8
9
10
11
void BuildTrie(const std::string& s)
{
	int x=0;
	for(int i=0;i<s.size();i++)
	{
		if(!AC[x].letter[s[i]-'a'])
			AC[x].letter[s[i]-'a'] = ind++; //ind为字典树组栈顶指针
		x=AC[x].letter[s[i]-'a'];
	}
	AC[x].cae++;
}

核心代码_求回溯数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void GetBtk()
{
	std::queue<int> q;
	for(int i=0;i<26;i++)
	{
		if(AC[0].letter[i])
		{
			AC[AC[0].letter[i]].btk=0;
			q.push(AC[0].letter[i]);
		}
	}
	while(q.size())
	{
		int cur=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(AC[cur].letter[i])
			{
				AC[AC[cur].letter[i]].btk = AC[AC[cur].btk].letter[i];
				q.push(AC[cur].letter[i]);
			}
			else  //防止因为走的路径问题错过本来可以匹配的对象
				AC[cur].letter[i] = AC[AC[cur].btk].letter[i];
		}
	}
}

核心代码_字符串匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int AC_Query()
{
	int cur=0,ans=0;
	for(int i=0;i<s.size();i++) //遍历文本串的每一个字母
	{
		cur = AC[cur].letter[s[i]-'a'];
		for(int t=cur;t&&AC[t].cae!=-1;t=AC[t].btk) //回溯的时候到了0就终止，如果cae等于-1说明此路来过
		{
			ans += AC[t].cae;
			AC[t].cae = -1;
		}
	}
	return ans;
}