算法基础05——字符串匹配
基本定义
假设文本是一个长度为n的数组T[1..n],而模式是一个长度为m的数组P[1..m]，其中 m ≤ n,进一步假设P和T的元素都是来自一个有限字母集 ∑ 的字符。例如 ∑ = ｛0，1｝或者∑ = ｛a,b, ... ,z｝。字符数组P和T通常称为字符串。
在数组T中，若偏移x位，即T[1+x，1+x+m] 与模式串 p相同，则成在T中模式P匹配。
要匹配的串称之为“模式”或“模式串”。
朴素匹配算法（BF算法）
最简单粗暴的办法，当然效率最低，非常"朴素"。
从待匹配的字符串头开始一次，依次和模式串中的每一位比较，如果不存在不相等，则将模式串整体后移一位继续比较。
两个for循环搞定，但是时间复杂度O（（m-n+1）m）
RK算法（Rabin-Karp算法）
M.O.Rabin和R.A.Karp发明了一种完全不同的基于散列的字符串匹配算法。我们需要计算模式串T的散列函数，然后利用相同的散列还是计算文本S中所有可能的M个字符串散列值并寻找匹配。如果找到了一个散列值后模式串相等的子字符串，那么在继续验证二者是否真的相同匹配。（回想散列表的取值，我们先通过hash算法获取到key在到key对应的数组中找值是否真的相等）。
这个过程相当于把模式串保存在一张散列表中，然后在文本的所以子字符串中进行查找。但不需要为散列表预留任何空间，因为它只有一个元素（也就是模式串）。
虽然看上去很简单，但事实上通过上述描述直接实现的算法会比朴素匹配算法还慢很多- -！这里的关键就在于hash算法
Rabin和Karp发明了一种能在常数时间内算出M个字符串散列值的方法（需要预处理），这样就得到了在实际应用中的运行时间为线性级别的字符串查找算法。
在实际应用中,RK算法可以很好的运行，并且还可以从中归纳出相关问题的其他算法（比如二维模式匹配）。RK算法预处理时间复杂度为O(m)，并且在最坏情况下运行时的复杂度为O((n-m+1)m)
RK的hash算法
长度为M的字符串对应着一个R进制的M位数。为了用一张大小为Q的散列表来保存这种类型的键，需要一个能将R进制的M位数转化为一个0 - Q-1之间的int值散列函数。一般最简单的办法是取模：将该数除以Q并取余数。在实际应用中会使用一个随机的素数Q，在不确定溢出的情况下选择一个尽可能大的值。(因为我们并不会真的需要一张散列表。)理解这个方法最简单的办法就是取一个较小的Q和R=10的情况
要在文本3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3中找到模式2 6 5 3 5,首先要选择散列表的大小Q(在这个例子中是997),则散列值为26535 % 997=613,然后计算文本中所有长度为5个数字的子字符串的散列值并寻找匹配。在这个例子中,在找到613的匹配之前,得到的散列值分别为508、201、715、971、442和929
上面我们直接用的由整型数字组成的字符串来进行的取模运算，但是如果是非整型或者长度非常长呢？
如果要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。
基于基数计数法：
如对于10进制：
123 = 1 * 102 + 2 * 101 + 3 * 100
对于26进制：
abc = 1 * 262 + 2 * 261 + 3 * 260
对于5位的数值,只需使用int值即可完成所有所需的计算。但如果M是100或者1000怎么办?这里使用的是 Horner方法。
//计算key[0..M-1]的散列值
private long hash(String key, int M){
long h = 0;
for(int j = 0; j < M; j++){
h = (R * h + key.charAt(j)) % Q;
}
return h;
}
这段代码计算了用char值数组表示的R进制的M位数的散列函数,所需时间与M成正比。(将作为参数传递给该方法,这样就可以将它同时用于模式字符串和正文。）对于这个数中的每一位数字,将散列值乘以R,加上这个数字,除以Q并取其余数。例如,这样计算示例模式字符串散列值的过程如图所示。我们也可以用同样的方法计算文本中的子字符串散列值,但这样一来字符串查找算法的成本就将是对文本中的每个字符进行乘法、加法和取余计算的成本之和。在最坏情况下这需要NM次操作,相对于暴力子字符串查找算法来说并没有任何改进
关键思想
Rabin-karp算法的基础是对于所有位置1,高效计算文本中i1位置的子字符串散列值。这可以由一个简单的数学公式得到。我们用ti表示txt. charat(i)也就是第i个字符,那么文本txt中起始于位置i的含有M个字符的子字符串所对应的数即为
假设已知(x)= x mod Q。将模式字符串右移一位即等价于将x替换为:
即将它减去第一个数字的值,乘以R,再加上最后一个数字的值。现在,关键的一点在于不需要保存这些数的值,而只需要保存它们除以Q之后的余数。取余操作的一个基本性质是如果在每次算术操作之后都将结果除以Q并取余,这等价于在完成了所有算术操作之后再将最后的结果除以Q并取余。这么做的结果就是无论M是5、100还是1000,都可以在常数时间内高效地不断向右.
首先保存 RM-1mod Q的值。 然后计算文本的前M个字母的散列值并将它和模式字符串的散列值进行比较。如果未能匹配它将会在文本中继续前进,用以上讨论的方法计算由位置i开始的M个字符的散列值,将它保存在变量中并将每个新的散列值与之进行比较,
用蒙特卡洛法验证正确性:
在文本txt中找到散列值与模式字符串相匹配的一个M个字符的子字符串之后，你可能会逐个比较它们的字符以确保得到了一个匹配而非相同的散列值。我们不会这么做，因为这需要回退文本指针。作为替代，这里将散列表的“规模"Q设为任意大的一个值，因为我们并不会真构造一张散列表而只是希望用模式字符串验证是否会产生冲突。我们会取一个大于1020的long型值，使得一个随机键的散列值与模式字符串冲突的概率小于10-20。这是一个极小的值。如果它还不够小，你可以将这种方法运行两遍，这样失败的几率将会小于10-40。这是蒙特卡洛算法一种著名早期应用，它既能够保证运行时间，失败的概率又非常小。检查匹配的其他方法可能很慢（性能有很小的概率相当于暴力算法）但能够确保正确性。这种算法被称为拉斯维加斯算法。
/**
* 字符串匹配 RK算法(BF算法的优化版) 性能比较低,用hash算法进行优化
*
* @author yixunfei
*
*/
public class StringRKMatching {
/*
* 描述： 其实就是在BF基础上对比较的0-m-n个子串求一个hash值，然后每次比较hash值是否相等取消掉内部的遍历比较
* 关键问题在于对hash算法的设计.最简单的，a-z直接用26进制表示，转化为10进制数...将字符转换为数字
*
* "cba" = c * 26 * 26 + b * 26 + a *1 = 1353
*
* dbcedb ||
*
* "【dbc】 edb" 3 * 26 * 26 + 1* 26 + 2
* "d 【bce】 de" 1*26*26+2*26+4
*
* 算法规律: h[i - 1]对应子串S[i - 1， i+m-2]的hash值，h[i]对应子串S[i,i+m-1]的hash值
* h[i - 1] = 26^(m-1) * (S[i-1]-'a') + 26^(m-2) * (s[i]-'a') + ...+26^0 * (S[i + m -2] -'a')
* h[i] = 26^(m-1) * (S[i]-'a') + ...+26^0 * (S[i + m -1] - 'a')
* 所以
* h[i] =(h[i - 1] - 26^(m-1) * (S[i-1] - 'a') * 26 + 26^0 * (S[i+m-1] - 'a'))
* PS:上面的公式可能有误，详细推论见《算法导论》第32章，Rabin-Karp算法（第三版580页）或 《算法》5.3
* 通过公式可以通过h[i - 1]计算出h[i]。前一个子串的hash直接计算后一个子串的hash值
* RK就是hash算法设计比较麻烦,在计算hashcode相同后，需要在比较一次字符串是否相等防止hash冲突(可以用26个素数表示a-
* z降低hash冲突概率...)
*
*/
private static int[] powValue;
static {
powValue = new int[30];
for(int i = 0; i < powValue.length; i++) {
powValue[i] = pow(26, i);
}
}
private static void initPowValue(int num) {
powValue = new int[num];
for(int i = 0; i < powValue.length; i++) {
powValue[i] = pow(26, i);
}
}
private static final int[] table = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101 };// 质数表对应a-z
public static int matching(String sourceTxt, String matchingTxt) {
int matchIndex = -1;
int n = sourceTxt.length();
int m = matchingTxt.length();
boolean isEquals = true;
if(m > n) {
return matchIndex;
}
//先把幂数求出来，不用每次都去计算
if(m > 30) {
initPowValue(m);
}
//相同长度直接遍历判断是否相等
if(m == n) {
for(int i = 0; i < m;i++) {
if(sourceTxt.charAt(i) != matchingTxt.charAt(i)) {
return matchIndex;
}
}
return 0;
}
// 先算出模式串的hash值
int matchTxtHashCode = 0;
for (int i = 0; i < m; i++) {
matchTxtHashCode += table[matchingTxt.charAt(i) - 'a'] * powValue[m - i - 1];
}
int hashCode = 0;
//计算第一个子串的hash值
for (int j = 0; j < m ; j++) {
hashCode += table[sourceTxt.charAt(j) - 'a'] * powValue[m - j - 1];
}
for (int i = 1; i < n - m; i++) {
// 计算子串的哈希值
//h[i] = 26 * (h[i-1] - 26^m-1 ) + s[t + m]
hashCode = 26 * (hashCode - powValue[ m-1]*table[sourceTxt.charAt(i) - 'a'] ) + table[sourceTxt.charAt(i + m ) - 'a'];
//这里还有很多优化方案，比如取模，判等之类的
if (hashCode == matchTxtHashCode) {
//TODO hashcode相等还要再判断值相等
for(int y = 0,z = i + 1; y < m; y++,z++) {
if(sourceTxt.charAt(z) != matchingTxt.charAt(y)) {
isEquals = false;
break;
}
}
if (isEquals) {
return i + 1;
}
}
}
return matchIndex;
}
public static int pow(int a,int b) {
//反复平方快速求幂。（int可能会溢出但并不影响，只需要hash。也可以加个求模）
int ret = 1;
int base = a;
while (b != 0) {
if ((b & 1) != 0)
ret *= base;
base *= base;
b >>= 1;
}
return ret;
}
public static void main(String[] args) {
System.err.println("还在初始化中....");
StringBuffer t = new StringBuffer();
//50000000中最差情况下的查找
for(int i = 0;i < 50000000;i++) {
t.append("a");
}
t.append("abcdefg");
String s = t.toString();
System.err.println("初始化完成...开始匹配");
long begin = System.currentTimeMillis();
int x= matching(s, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcdefg");
long end = System.currentTimeMillis();
System.err.println(end - begin + "ms" + "\t" + x);
}
}
BM算法
在计算机科学里，Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串（关键字）进行预处理，而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。
定义：
1. S[i]为字符串S从1开始排列的第i个字符
2. S[i..j]为字符串S的一个子串，始于i，终于j。
3. S的前缀定义为S[1..i],1<i<n，n为字符串S的长度。
4. S的后缀定义为S[i..n],1<i<=n，小于字符串S的长度。
5. 检索的字符串称为pattern，用符号P表示。
6. 被检索字符称为text，用符号T表示。
7. P的长度为n
8. T的长度为m
9. k表示P的最后一个字符在T中的位置。
10. 当匹配发生时，P在T中的位置为T[(k-n+1)..k]。
不同于朴素模式（brute-force search）的逐个字符对比，Boyer-Moore充分使用预处理P的信息来尽可能跳过更多的字符。通常，我们比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较。这样，就需要将字串中的所有字符一一比较。Boyer-Moore算法的关键在于，当P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。如果最后一个字符未在P中出现，那么我们可以直接跳过T的n个字符，比较接下来的n个字符，n为P的长度（见定义）。如果最后一个字符出现在P中，那么跳过的字符数需要进行计算（也就是将P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。
形式化的表述方式为，从k=n开始，也就是P从T的最开始进行比较。紧接着，P的第n个字符和T的第k个字符开始：字符串依次从P的最后一个字符到最开始的字符。结束条件是当比较到达P的最开始（此时匹配完成），或按照规则移动后的字符部匹配发生时。然后，在新的对齐位置重新开始比较，如此反复，直到到达T的结尾。
移动规则是一张间恒定的查找表，通过对P的预处理产生的。
移动字符数是通过两条规则决定的：坏字符规则和好后缀规则。实际移动为通过这两条规则计算出的最大移动个数。
我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。我举个例子解释一下，你可以看我画的这幅图。
在这个例子里，主串中的 c，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 c 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 c 的后面。
由现象找规律，你可以思考一下，当遇到不匹配的字符时，有什么固定的规律，可以将模式串往后多滑动几位呢？这样一次性往后滑动好几位，那匹配的效率岂不是就提高了？我们今天要讲的 BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
BM 算法原理
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来看，这两个规则分别都是怎么工作的。
1.坏字符规则
RK和BF在匹配的过程中，我们都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。我画了一张图，你可以看下。
我们从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。
我们从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。
我们拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 c 与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往后滑动三位，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较。
这个时候，我们发现，模式串中最后一个字符 d，还是无法跟主串中的 a 匹配，这个时候，还能将模式串往后滑动三位吗？答案是不行的。因为这个时候，坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。
第一次不匹配的时候，我们滑动了三位，第二次不匹配的时候，我们将模式串后移两位，那具体滑动多少位，到底有没有规律呢？当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，我这里说的下标，都是字符在模式串的下标）。
这里我要特别说明一点，如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。
比如，主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。
好后缀规则
好后缀规则实际上跟坏字符规则的思路很类似。你看我下面这幅图。当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。
这个时候该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计算模式串的滑动位数，不过，我们也可以使用好后缀处理规则。两种规则到底如何选择，我稍后会讲。抛开这个问题，现在我们来看，好后缀规则是怎么工作的？
我们把已经匹配的 bc 叫作好后缀，记作。我们拿它在模式串中查找，如果找到了另一个跟相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串中对齐的位置。
如果在模式串中找不到另一个等于的子串，我们就直接将模式串，滑动到主串中的后面，因为之前的任何一次往后滑动，都没有匹配主串中的情况。
不过，当模式串中不存在等于的子串时，我们直接将模式串滑动到主串的后面。这样做是否有点太过头呢？我们来看下面这个例子。这里面 bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串{u*}，但是如果我们将模式串移动到好后缀的后面，如图所示，那就会错过模式串和主串可以匹配的情况。
如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。
所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。
所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是，然后将模式串滑动到如图所示的位置。
坏字符和好后缀的基本原理都讲完了，我现在回答一下前面那个问题。当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的位数？
我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免我们前面提到的，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。
public class StringBMMatching {
public static int pattern(String sourceTxt, String matchTxt) {
int matchLength = matchTxt.length();
int sourceLength = sourceTxt.length();
if (sourceLength > matchLength) {
return -1;
}
int[] badTable = createBadTable(sourceTxt);
int[] goodTable = createGoodTable(sourceTxt);
for (int i = sourceLength - 1, j; i < matchLength;) {
System.out.println("跳跃位置：" + i);
for (j = sourceLength - 1; matchTxt.charAt(i) == sourceTxt.charAt(j); i--, j--) {
if (j == 0) {
System.out.println("匹配成功，位置：" + i);
// i++; // 多次匹配
// break;
return i;
}
}
i += Math.max(goodTable[sourceLength - j - 1], badTable[matchTxt.charAt(i)]);
}
return -1;
}
/**
* 字符信息表
*/
public static int[] createBadTable(String match) {
//FIXME 这里用hash表更好
final int tableSize = 256;
int[] badTable = new int[tableSize];
int mLen = match.length();
for (int i = 0; i < badTable.length; i++) {
//默认初始化全部为匹配字符串长度
badTable[i] = mLen;
}
for (int i = 0; i < mLen - 1; i++) {
int k = match.charAt(i);
badTable[k] = mLen - 1 - i;
}
return badTable;
}
/**
* 匹配偏移表。
*
* @param match
* 模式串
* @return
*/
public static int[] createGoodTable(String match) {
int mLength = match.length();
int[] goodTable = new int[mLength];
int lastPrefixPosition = mLength;
for (int i = mLength - 1; i >= 0; --i) {
if (isPrefix(match, i + 1)) {
lastPrefixPosition = i + 1;
}
goodTable[mLength - 1 - i] = lastPrefixPosition - i + mLength - 1;
}
for (int i = 0; i < mLength - 1; ++i) {
int slen = suffixLength(match, i);
goodTable[slen] = mLength - 1 - i + slen;
}
return goodTable;
}
/**
* 前缀匹配
*/
private static boolean isPrefix(String pattern, int p) {
int patternLength = pattern.length();
for (int i = p, j = 0; i < patternLength; ++i, ++j) {
if (pattern.charAt(i) != pattern.charAt(j)) {
return false;
}
}
return true;
}
/**
* 后缀匹配
*/
private static int suffixLength(String pattern, int p) {
int pLen = pattern.length();
int len = 0;
for (int i = p, j = pLen - 1; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) {
len += 1;
}
return len;
}
}
KMP算法
Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。
这个算法是由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终由三人于1977年联合发表。
查找算法实例
我们用一个实例来演示这个算法。在任意给定时间，本算法被两个整数m和i所决定：
- m代表主文字符串S内匹配字符串W的当前查找位置，
- i代表匹配字符串W当前做比较的字符位置。
图示如下：
我们从W与S的开头比较起。我们比对到S[3](=' ')时，发现W3与其不符。接着并不是从S[1]比较下去。我们已经知道S[1]~S[3]不与W[0]相合。因此，略过这些字符，令m = 4以及i = 0。
如上所示，我们检核了"ABCDAB"这个字符串。然而，这与目标仍有些差异。我们可以注意到，"AB"在字符串头尾处出现了两次。这意味着尾端的"AB"可以作为下次比较的起始点。因此，我们令m = 8, i = 2，继续比较。图标如下：
于m = 10的地方，又出现不相符的情况。类似地，令m = 11, i = 0继续比较：
这时，S17不与W[6]相同，但是亦出现了两次"AB"，我们采取一贯的作法，令m = 15和i = 2，继续搜索。
我们找到完全匹配的字符串了，其起始位置于S[15]的地方。
部分匹配表(PMT)
部分匹配表，又称为失配函数，作用是让算法无需多次匹配S中的任何字符。能够实现线性时间搜索的关键是在主串的一些字段中检查模式串的初始字段，我们可以确切地知道在当前位置之前的一个潜在匹配的位置。换句话说，在不错过任何潜在匹配的情况下，我们"预搜索"这个模式串本身并将其译成一个包含所有可能失配的位置对应可以绕过最多无效字符的列表。
对于W中的任何位置，我们都希望能够查询那个位置前（不包括那个位置）有可能的W的最长初始字段的长度，而不是从W[0]开始失配的整个字段，这长度就是我们查找下一个匹配时回退的距离。因此T[i]是W的可能的适当初始字段同时也是结束于W[i - 1]的子串的最大长度。我们使空串长度是0。当一个失配出现在模式串的最开始，这是特殊情况（无法回退），我们设置T[0] = -1，在下面讨论。
创建表算法示例
我们首先考虑例子W = "ABCDABD"。使用这个大致相同的模式串作为主搜索，我们将会看到它高效的原因。
首先，我们设定T[0] = -1。为了找到T[1]，我们必须找到一个"A"的适当后缀同时也是W的前缀。但"A"没有后缀，所以我们设定T[1] = 0。类似地，T[2] = 0。
继续到T[3]，我们注意到检查所有后缀有一个捷径：假设我们发现了一个适当后缀，结束于W[2]、长度为2（最大可能）的后缀，那么它的第一个字符是W的一个适当前缀。因此一个结束于W[1]的适当前缀，我们已经确定了不可能出现在T[2]。因此在每一层递推中，这个规则是只有在上一层找到一个长度为m的有效后缀时，才需要检查给定长度为m+1的后缀（例如，T[x]=m）。
那么我们甚至不需要关心具有长度为2的子串，由于上一个情况因长度为1而失配，所以T[3] = 0。
我们继续遍历到W[4]子序列，'A'。同样的逻辑说明我们需要考虑的最长子串的长度是1，并且在'A'这个情况中有效，回退到我们寻找的当前字符之前的字段，因此T[4] = 0。
现在考虑下一个字符W[5]，'B'，我们使用这样的逻辑：如果我们曾发现一个子模式在上一个字符W[4]之前出现，继续到当前字符W[5]，那么在它之前它本身会拥有一个结束于W[4]合适的初始段，与事实相反的是我们已经找到'A'是最早出现在结束于W[4]的合适字段。因此为了找到W[5]的终止串，我们不需要查看W[4]。因此T[5] = 1。
最后，我们看到W[4] = 'A'下一个字符是'B'，并且这也确实是W[5]。此外，上面的相同参数说明为了查找W[6]的字段，我们不需要向前查看W[4]，所以我们得出T[6] = 2。
于是我们得到下面的表：
另一个更复杂和有趣的例子：
如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。同样可以定义后缀A=SB， 其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。
PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长 度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。
KMP本质上就是通过上述的PMT表完成优化。
/**
* KMP 匹配算法 更加通用的一种匹配算法,虽然名气很大但是性能其实不如BM算法,比BM算法更适用于模式串较小的情况.
* 把模式串的前缀子串和主串的后缀子串比较. 从不匹配的坏字符开始，将可以匹配部分原串的后缀串与模式串的前缀串依次比较取最大匹配的子串，然后移动对齐即可
* 主 串：a b (a b a好前缀的后缀子串) [f 坏字符] a b a m
* 模式串：(a b a好前缀的前缀子串) b a [m]
*
* 将模式串的前缀子串集中放到数组中,每次直接比较
*
*/
public class KMPMatching {
/*
*/
public static int matching(String sourceTxt, String matchTxt) {
//toCharArray在内部多创建一个数组，可以改成CharAt
return kmp(sourceTxt.toCharArray(), matchTxt.toCharArray());
}
/**
* KMP 匹配算法
* @param sourceTxt 主串
* @param matchTxt 模式串
* @return 匹配到模式串中的下标
*/
public static int kmp(char[] sourceTxt, char[] matchTxt) {
int ret = -1;
int sourceLength = sourceTxt.length;
int matchLength = matchTxt.length;
int[] next = getNexts(matchTxt, matchLength);
int j = 0;
for (int i = 0; i < sourceLength; ++i) {
while (j > 0 && sourceTxt[i] != matchTxt[j]) { // 一直找到 a[i] 和 b[j]
j = next[j - 1] + 1;
}
if (sourceTxt[i] == matchTxt[j]) {
++j;
}
// 找到匹配模式串的了
if (j == matchLength) {
ret = i - matchLength + 1;
return ret;
}
}
return ret;
}
// b 表示模式串，m 表示模式串的长度
private static int[] getNexts(char[] match,int matchLength) {
int[] next = new int[matchLength];
next[0] = -1;
int k = -1;
for (int i = 1; i < matchLength; ++i) {
while (k != -1 && match[k + 1] != match[i]) {
k = next[k];
}
if (match[k + 1] == match[i]) {
++k;
}
next[i] = k;
}
return next;
}
}
AC自动机
Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。
从上面我们可以知道，ac自动机其实就是一种多模匹配算法，那么你可能会问什么叫做多模匹配算法。下面是我对多模匹配的理解，与多模与之对于的是单模，单模就是给你一个单词，然后给你一个字符串，问你这个单词是否在这个字符串中出现过（匹配），这个问题可以用kmp算法在比较高效的效率上完成这个任务。那么现在我们换个问题，给你很多个单词，然后给你一段字符串，问你有多少个单词在这个字符串中出现过，当然我们暴力做，用每一个单词对字符串做kmp,这样虽然理论上可行，但是时间复杂度非常之高，当单词的个数比较多并且字符串很长的情况下不能有效的解决这个问题，所以这时候就要用到我们的ac自动机算法了。
AC 自动机是 以字典树的结构为基础 ，结合 KMP 的思想建立的。
简单来说，建立一个 AC 自动机有两个步骤：
- 基础的 TRIE 结构：将所有的模式串构成一棵 。
- KMP 的思想：对树上所有的结点构造失配指针。
然后就可以利用它进行多模式匹配了。
字典树构建
AC 自动机在初始时会将若干个模式串丢到一个 TRIE 里，然后在 TRIE 上建立 AC 自动机。这个 TRIE 就是普通的 TRIE，该怎么建怎么建。这里需要仔细解释一下 TRIE 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。TRIE 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，TRIE 的边就是状态的转移。
形式化地说，对于若干个模式串s1,s2,...,sn ，将它们构建一棵字典树后的所有状态的集合记作 Q 。
失配指针
AC 自动机利用一个 fail 指针来辅助多模式串的匹配。
状态u的 fail 指针指向另一个状态v，其中v ∈ Q ，且 v 是 u 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针：
- 共同点：两者同样是在失配的时候用于跳转的指针。
- 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。
因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。
AC 自动机的失配指针指向当前状态的最长后缀状态，AC 自动机在做匹配时，同一位上可匹配多个模式串。
构建指针
构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想。考虑字典树中当前的结点u，u 的父结点是p ，p通过字符 c 的边指向u，即 tire[p,c] = u 。假设深度小于u 的所有结点的 fail 指针都已求得。
- 如果 trie[fail[p],c]存在：则让 u 的 fail 指针指向trie[fail[p],c]。相当于在p和 fail[p] 后面加一个字符 c ，分别对应u和fail[u] 。
- 如果 trie[fail[p],c] 不存在：那么我们继续找到 trie[fail[fail[p]],c]。重复 1 的判断过程，一直跳 fail 指针直到根结点。
如果真的没有，就让 fail 指针指向根结点。
如此即完成了fail[u]的构建。
例
对字符串 i he his she hers 组成的字典树构建 fail 指针：
黄色结点：当前的结点u。
绿色结点：表示已经 BFS 遍历完毕的结点，
橙色的边：fail 指针。
红色的边：当前求出的 fail 指针。
我们重点分析结点 6 的 fail 指针构建：
找到 6 的父结点 5，fail[5] = 10。然而 10 结点没有字母 s 连出的边；继续跳到 10 的 fail 指针，fail[10] = 0 。发现 0 结点有字母 s 连出的边，指向 7 结点；所以fail[6] = 7.
字典树与字典图
将结点按 BFS 顺序入队，依次求 fail 指针。这里的字典树根结点为 0，我们将根结点的子结点一一入队。若将根结点入队，则在第一次 BFS 的时候，会将根结点儿子的 fail 指针标记为本身。因此我们将根结点的儿子一一入队，而不是将根结点入队。
然后开始 BFS：每次取出队首的结点 u。fail[u]指针已经求得，我们要求 u 的子结点们的 fail 指针。然后遍历字符集（这里是 0-25，对应 a-z）：
- 如果 trans(u,i) 存在，我们就将trans(u,i) 的 fail 指针赋值为trans(fail[u],i)。这里似乎有一个问题。根据之前的讲解，我们应该用 while 循环，不停的跳 fail 指针，判断是否存在字符 i 对应的结点，然后赋值。不过在代码中我们一句话就做完这件事了。
- 否则，trans(u,i) 不存在，就让trans(u,i) 指向trans(fail[u],i) 的状态。
- 蓝色结点：BFS 遍历到的结点 u
- 蓝色的边：当前结点下，AC 自动机修改字典树结构连出的边。
- 黑色的边：AC 自动机修改字典树结构连出的边。
- 红色的边：当前结点求出的 fail 指针
- 黄色的边：fail 指针
- 灰色的边：字典树的边
可以发现，众多交错的黑色边将字典树变成了 字典图 。图中省 s 略了连向根结点的黑边（否则会更乱）。我们重点分析一下结点 5 遍历时的情况。我们求trans(5,s) = 6 的 fail 指针：
本来的策略是找 fail 指针，于是我们跳到fail[5] = 10发现没有 s 连出的字典树的边，于是跳到fail[10]=0，发现有tire[0,s] =7，于是 fail[6] = 7；但是有了黑边、蓝边，我们跳到fail[5]=10 之后直接走trans(10,s)=7 就走到 7号结点了
多模式匹配
我们从根结点开始尝试匹配 ushersheishis ，那么 p 的变化将是：
- 红色结点：p 结点
- 粉色箭头：p 在自动机上的跳转，
- 蓝色的边：成功匹配的模式串
- 蓝色结点：示跳 fail 指针时的结点（状态）。
AC 自动机的时间复杂度在需要找到所有匹配位置时是O(s + m)，其中s表示文本串的长度，m表示模板串的总匹配次数；而只需要求是否匹配时时间复杂度为O（s)。
确定有限状态自动机
有限状态自动机（deterministic finite automaton，DFA）是由 1. 状态集合Q； 2. 字符集∑； 3. 状态转移函数 δ：Q x ∑ → Q ，即δ（q，σ）= q',q,q' ∈ Q，σ ∈ ∑ ； 4. 一个开始状态s ∈ Q ； 5. 一个接收的状态集合 F ⊆ Q 。组成的五元组（Q,∑,δ,s,F） 。
用 AC 自动机理解，状态集合就是字典树（图）的结点；字符集就是 a 到 z （或者更多）；状态转移函数就是trans(u,c) 的函数（即 tr[u,c] ）；开始状态就是字典树的根结点；接收状态就是你在字典树中标记的字符串结尾结点组成的集合。
KMP自动机
KMP 自动机就是一个不断读入待匹配串，每次匹配时走到接受状态的 DFA。如果共有 m个状态，第i个状态表示已经匹配了前 i个字符。那么我们定义transi,c 表示状态i读入字符c后到达的状态，nexti表示 prefix function ，则有： （约定 next0 =0 ）
我们发现 transi只依赖于之前的值，所以可以跟 KMP 一起求出来。
时间和空间复杂度：O(m|∑|)。一些细节：走到接受状态之后立即转移到该状态的next。
对比之下，AC 自动机其实就是 Trie 上的自动机。
/**
* AC自动机 其实就是字典树的优化 多模式串匹配
* 在Tire树基础上添加失败指针（和KMP差不多）
* 基于多模式串创建Tire树
* 在树上创建失败指针
*/
public class ACMatching {
private ACNode root;
public ACMatching() {
this.root = new ACNode("/");
}
private void insert(String pattern) {
ACNode node = this.root;
int len = pattern.length();
for (int i = 0; i < len; i++) {
String c = pattern.charAt(i) + "";
if (Objects.isNull(node.children.get(c))) {
node.children.put(c, new ACNode(c));
}
node = node.children.get(c);
}
node.isEndingChar = true;
node.length = pattern.length();
}
private void buildFailurePointer() {
ACNode root = this.root;
LinkedList<ACNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
ACNode p = queue.pop();
for (ACNode pc : p.children.values()) {
if (Objects.isNull(pc)) {
continue;
}
if (p == root) {
pc.fail = root;
} else {
ACNode q = p.fail;
while (Objects.nonNull(q)) {
ACNode qc = q.children.get(pc.data);
if (Objects.nonNull(qc)) {
pc.fail = qc;
break;
}
q = q.fail;
}
if (Objects.isNull(q)) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}
private Boolean match(String text) {
ACNode root = this.root;
ACNode p = root;
int n = text.length();
for (int i = 0; i < n; i++) {
String c = text.charAt(i) + "";
while (Objects.isNull(p.children.get(c)) && p != root) {
p = p.fail;
}
p = p.children.get(c);
if (Objects.isNull(p)) {
p = root;
}
ACNode tmp = p;
while (tmp != root) {
if (tmp.isEndingChar == true) {
System.out.println("Start from " + (i - p.length + 1));
return true;
}
tmp = tmp.fail;
}
}
return false;
}
public static boolean match(String text, String[] patterns) {
ACMatching automata = new ACMatching();
for (String pattern : patterns) {
automata.insert(pattern);
}
automata.buildFailurePointer();
return automata.match(text);
}
public class ACNode {
private String data;
private Map<String, ACNode> children;
private Boolean isEndingChar;
private Integer length;
private ACNode fail;
public ACNode(String data) {
this.data = data;
this.children = new HashMap<>();
this.isEndingChar = false;
this.length = 0;
this.fail = null;
}
}
}
更新时间：2020-09-14 21:06:53
本文由 寻非 创作，如果您觉得本文不错，请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
原文链接：https://www.zhouning.group/archives/算法基础05字符串匹配
最后更新：2020-09-14 21:06:53
