4.2.2 字符串的模式匹配
字符串有一类重要的运算，称为模式匹配（Pattern Matching）。设T和P是两个字符串（T的长度为n，P的长度为m，1≤m≤n），称T为目标（Target），P为模式（Pattern），要求在T中查找是否有与P相等的子串。如果有，则给出P在T中的匹配位置，这个运算被称为模式匹配。模式匹配的方法主要有两种：
·朴素的模式匹配算法，也称为Brute Force算法；
·D.E.Knuth、J.H.Morris和V.R.Pratt提出的KMP算法。
1.Brute Force算法
Brute Force算法是模式匹配的一种最简单的做法，按顺序遍历T的字符串，将T的每个字符作为匹配的起始字符，用P的字符依次与T中的字符做比较，判断是否匹配。如果T和P的当前字符匹配，则比较下一个字符；否则，以T的当前起始字符的下个字符为起始字符，重复上述步骤。如果T的一个子字符串与P匹配，则返回T中的匹配子串的起始字符的序号，匹配成功；如果在T中不存在与P匹配的子字符串，则匹配失败。
Brute Force算法的时间复杂度为O((n-m+1)m)。
【4.2.2.1 Blue Jeans】
地理项目是IBM和美国国家地理学会的合作研究项目，该项目基于成千上万捐献的DNA，来分析地球上的人类是如何繁衍的。
作为一个IBM的研究人员，请你编写一个程序找出给定的DNA片段间的相同之处，使对个体的调查相关联。
一个DNA碱基序列是指把在分子中发现的氮基的序列罗列出来。有四种氮基：腺嘌呤（A）、胸腺嘧啶（T）、鸟嘌呤（G）和胞嘧啶（C）。例如，一个6碱基DNA序列可以表示为TAGACC。
给出一个DNA碱基序列的集合，确定在所有序列中都出现的最长的碱基序列。
输入
输入的第一行给出了整数n，表示测试用例的数目。每个测试用例由下述两部分组成：
·一个正整数m（2≤m≤10），给出该测试用例中碱基序列的数目。
·m行，每行给出一个60碱基的碱基序列。
输出
对于输入的每个测试用例的所有碱基序列，输出最长的相同的碱基子序列。如果最长的相同的碱基子序列的长度小于3，则输出“no significant commonalities”来代替碱基子序列。如果相同最长长度的子序列有多个，则仅输出按字母排序的第一个。
试题来源：ACM South Central USA 2006
在线测试：POJ 3080，ZOJ 2784，UVA 3628
试题解析
设最长公共子串为ans，其长度为len；m个碱基序列为p[0]…p[m-1]。
由于公共子序列是每个碱基序列的子串，因此枚举p[0]的每一个可能的子串s，以s为模式、分别以p[1]…p[m-1]为目标，进行匹配计算。
若s为p[1]…p[m-1]的公共子串（strstr(p[k],s)!=NULL，1≤k≤m-1)，且（s串的长度>len），或者s的长度虽等于len，但字典序小于目前最长的公共子串ans（strcmp(ans,s)>0），则将s调整为最长公共子串（len=串s的长度；strcpy(ans,s)）。
在p[0]的所有子串被枚举后，最终得出的最长公共子串ans即问题解。
由于碱基序列的串长仅为60，因此计算子串匹配时采用了Brute Force算法。另外使用了一些字符串库函数，例如字符串长度函数strlen()、比较字符串大小的函数strcmp()、字符串复制函数strcpy()等，使程序更加清晰和简练。
参考程序
#include <cstdio> //预编译命令
#include <cstring>
const int maxm = 10 + 5; //碱基序列数的上限
const int maxs = 60 + 5; //串长上限
int main(void)
{
int loop;
scanf("%d", &loop); //输入测试用例数
while (loop--) {
int m;
char p[maxm][maxs];
scanf("%d", &m); //输入碱基序列的数目
for (int i = 0; i < m; i++) //输入第i个碱基序列
scanf("%s", p[i]);
int len; //最长公共子串的长度
char ans[maxs]; //最长公共子串
len = 0;
//枚举p[0]的每个子串，判断其是否为目标子串
for (int i = 0; i < strlen(p[0]); i++) //枚举子串的起始位置i
for (int j = i + 2; j < strlen(p[0]); j++) { //枚举子串的结束位置j
char s[maxs]; //提取该子串s
strncpy(s, p[0] + i, j - i + 1);
s[j - i + 1] = '\0';
bool ok = true; //试探s是否为p[1]..p[m-1]的公共子串
for (int k = 1; ok && k < m; k++)
if (strstr(p[k], s) == NULL) ok = false;
//若s是目前最长的公共子串，或者虽然s同属最长公共子串但字典序小，则s被设为最长公共子串
if (ok && (j - i + 1 > len || j - i + 1 == len && strcmp(ans, s) > 0))
{
len = j - i + 1;
strcpy(ans, s);
}
}
if (len < 3) //若最长的公共子串的长度不足3，则给出失败信息，否则输出最长公共子串
printf("%s\n", "no significant commonalities");
else printf("%s\n", ans);
}
return 0;
}
Brute Force算法并不完美，存在着大量的重复运算，如图4.2-1所示。
图 4.2-1
模式P=“ATATACG”的第6个字符“C”在当前位置无法匹配，Brute Force算法将指针s递增1，再从P的第一个字符开始重新匹配，但实际上此时可以将指针s递增2，从P的第4个字符开始匹配，如图4.2-2所示。因为在这之间的匹配肯定会失败。类似的例子会随着数据量的增大而越来越多，Brute Force算法将做更多的重复工作。
图 4.2-2
为了避免重复运算，提高匹配时效，基于上述讨论，给出模式匹配的KMP算法。
2.KMP算法
分析图4.2-2，为什么可以让指针s递增2，从P的第4个字符开始匹配呢？这是由模式P的性质决定的。对于模式P，在目标T中，P的前缀“ATATA”已经匹配。
对已经匹配的P的前缀“ATATA”进行分析，如图4.2-3所示，P的前缀“ATA”恰好是P已经匹配的前缀“ATATA”的后缀，所以如果直到“ATATA”都匹配成功，而“ATATAC”匹配失败，则目标T的子串T[s+2..s+4]必定为“ATA”，因为“ATATA”在s处匹配成功，所以T[s..s+4]=“ATATA”，于是P的前缀“ATA”肯定在s+2处匹配成功。KMP算法正是利用了这种特性使算法的时间复杂度降为O(n+m)。
图 4.2-3
KMP算法的关键是求P的前缀函数suffix[]，其中，suffix[q]=max{k|(k<q)∧(P[0..k-1]==P[0..q-1]的后缀)}，也就是说，suffix[q]表示P[0..q-1]的后缀与P的前缀间的最长匹配子串的长度。求suffix[]实际上就相当于用P匹配P的过程，可写成一重循环的形式：
suffix[0] = -1; //设置P的前缀函数suffix[]的边界值
suffix[1] = 0;
int k = 0; //前缀函数指针初始化
for (int i = 2; i <= m; i++) {
while (k>=0 && p[k]!=p[i - 1]) //沿前缀函数指针追溯P中与p[i-1]相同的字符位置k，即
//目标串当前字符与p[i]匹配失败时，应与p[k+1]比较；
//如果p[k]和p[i-1]不同，说明匹配失败，要把k的值退
//到suffix[k]，直到两者相同才停止
k = suffix[k];
suffix[i] = ++k;
}
有了前缀函数suffix[]，可将P匹配T的过程写成一重循环，从P[0]出发，依次匹配T[0],T[1],…,T[n-1]：
·若P[j]与T[i]匹配成功，则下一次匹配P[j+1]与T[i+1]。
·若P[j]与T[i]匹配失败，则T[i]不断匹配P[suffix[j]]、P[P[suffix[j]]]，…，直至匹配成功（T[i]==P[…P[suffix[j]]]）或者匹配失败（P[…P[suffix[j]]]==-1）为止。若匹配成功，则下一次比较P[P[…P[suffix[j]]]+1]与T[i+1]；若匹配失败，则下一次比较P[0]与T[i+1]（0≤i≤n-1，0≤j≤m-1）。
i=0; // T和P的匹配指针初始化
j=0；
while (i<=n-1 && j<=m-1)
if (j==-1||T[i]==P[j]) //若沿前缀函数指针匹配T[i]失败，则下一次比较P[0]与T[i+1]；若匹
//配成功，则下一次比较P[j+1]与T[i+1]
{
i++；j++;
}
else j= suffix[j]； //若T[i]与P[j]匹配失败，则沿前缀函数指针回溯
if (j>m-1) //若P中的所有字符配对成功，则返回P在T的匹配位置；否则返回-1
{
return(i-(m-1));
}
else return(-1);
【4.2.2.2 Oulipo】
法国作家Georges Perec（1936—1982）曾经写过一本没有字母e的书La Disparition，他是Oulipo组织的成员。从他的书中摘录如下：
Tout avait Pair normal,mais tout s’affirmait faux.Tout avait Fair normal,d’abord,puis surgissait l’inhumain,l’affolant.Il aurait voulu savoir oùs’articulait l’association qui l’unissait au roman:stir son tapis,assaillantàtout instant son imagination,l’intuition d’un tabou,la vision d’un mal obscur,d’un quoi vacant,d’un non-dit:la vision,l’avision d’un oubli commandant tout,oùs’abolissait la raison:tout avait l’air normal mais…
Perec可能会在这样的比赛中取得高分（或更确切地说，低分）。这些比赛要求人们写一段有关某个主题的有意义的文字，某个给定的词要尽可能少地出现。我们的工作是给出一个评判程序，统计该词出现的次数，以给出参赛者的排名。这些参赛者通常会写很长的废话连篇的文本，一个带500 000个连续的T的序列是常见的，而且他们从来不使用空格。
因此，给出一个字符串，我们要快速发现这个字符串在一段文本中出现的次数。更规范地讲：给出字母表{'A','B','C',…,'Z'}，以及字母表上的两个有限的字符串，即一个单词w和一段文本t，计算w在t中出现的次数。所有w的连续字符必须严格匹配t的连续字符。在文本t中，单词w的出现可能会重叠在一起。
输入
输入文件的第一行给出一个整数，该整数是后面给出的测试用例的个数。每个测试用例的格式如下。
一行给出单词w和一个在字母表{'A','B','C',…,'Z'}上的字符串，其中1≤|w|≤10 000（|w|表示字符串w的长度）。
一行给出文本t和一个在字母表{'A','B','C',…,'Z'}上的字符串，其中|w|≤|t|≤1 000 000。
输出
对于输入文件中的每个测试用例，在一行中输出一个数字：单词w在文本t中出现的次数。
试题来源：BAPC 2006 Qualification
在线测试：POJ 3461
试题解析
由于是计算单词w在文本t中的出现次数，因此w是模式，t是目标。我们先应用KMP算法计算出单词w的后缀函数next，然后使用next计算单词w在文本t中出现的频率cnt。计算方法如下。
设w的匹配指针为p，t的匹配指针为cur。初始时，p=0，cur=0。然后，逐个字符地扫描t：
1）若t和w的当前字符相同（t[cur]==w[p]），则w和t的指针各右移1个位置（++cur，++p）。
2）若t和w的当前字符不同（t[cur]≠w[p]），则分析：
·若未分析完w的所有字符（p≥0），则根据next数组左移w的指针（p=next[p]）。
·若分析完w的所有字符（p<0），则t的下一字符与w的首字符匹配（++cur，p=0）。
3）若匹配成功（p==w的长度），则单词w在t中的频率cnt++；根据next数组左移w的指针（p=next[p]），继续匹配t的下一个字符。
整个匹配过程进行至cur≥t的长度为止。此时得出的cnt即单词w在文本t中的出现次数。
参考程序
#include <cstdio> //预编译命令
#include <cstring>
const int maxw = 10000 + 10; //单词w的长度上限
const int maxt = 1000000 + 10; //文本t的长度上限
int match(char w[], char s[], int next[])
{ // 统计w[]在s[]中出现的次数
int cnt = 0; // w[]在s[]中的频率初始化
int slen = strlen(s); //计算s和w的串长
int wlen = strlen(w);
int p = 0, cur = 0; //w和s的指针初始化
while (cur < slen) { //若未扫描完s的所有字符
if (s[cur] == w[p]) { //若s和w的当前字符相同，则w和s的指针
//右移1个位置
++cur;
++p;
} else if (p >= 0) { //若未分析完w的所有字符，则根据next数组
//左移w的指针；否则s 的下一个字符与w的第1个字符匹配
p = next[p];
} else {
++cur;
p = 0;
}
if (p == wlen) { //若匹配成功，则w[]在s[]中的频率+1；根
//据next数组左移w[]的指针，从s[]的下一个字符开始继续匹配
++cnt;
p = next[p];
}
}
return cnt;
}
int main(void)
{
int loop;
scanf("%d", &loop); //输入测试用例数
while (loop--) {
char w[maxw], t[maxt];
scanf("%s%s", w, t); //输入单词w和文本t
int suffix[maxw]; //应用KMP算法计算单词w的前缀函数
suffix[0] = -1;
suffix[1] = 0;
int p = 0;
for (int cur = 2; cur <= strlen(w); cur++) {
while (p >= 0 && w[p] != w[cur - 1])
p = suffix[p];
suffix[cur] = ++p;
}
printf("%d\n", match(w, t, suffix)); //计算和输出单词w在文本t中的出现次数
}
return 0;
}