Joyce' Blog
0%

KMP算法

发表于 更新于

字符串匹配算法

给定主串A和模式串B，判断B是否是A的子串，并返回B在A中第一次出现的位置。

暴力算法BF算法

BruteForce的缩写。对主串和模式串进行逐个字符的对比。假设主串的长度是m，模式串的长度是n，需要m-n轮循环，每一轮里面，把模式串的位置右移一位，重新与主串对应位置进行匹配。

在某些极端情况下效率很低，例如：主串为aaaaaaaaaaaaaaab，模式串为aaab，在每一轮进行字符匹配时，模式串的前三个字符a都和主串中的字符相匹配，一直检查到模式串最后一个字符b，才发现不匹配。

在这种极端情况下，BF算法的最坏时间复杂度是O（mn）。

利用哈希值进行比较RK算法

Rabin-Karp的缩写。BF算法只是简单粗暴地对两个字符串的所有字符依次比较，而RK算法比较的是两个字符串的哈希值。没一个字符串都可以通过某种哈希算法，转换成一个整数型（hashcode）。

生成hashcode的算法

假设字符串只包含26个小写字母。

按位相加

a——1，b——2，c——3，……，把字符串的所有字符相加，结果作为hashcode。

做法简单但容易产生hash冲突，如abc、bac、cab的hashcode一样。两个hash值相等不一定两个字符串也相等，还需要进一步验证。

转换成26进制数

既然字符串只包含26个小写字母，可以把每一个字符串当成一个26进制数来计算。这样可以大幅减少hash冲突，但计算量较大，有可能出现超出整数范围的情况，因此需要对计算结果进行取模。

1
bce = 2*(26^2) + 3*26 + 5 = 1435

这里采用比较简单的按位相加的方法，代码如下

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static int rabinKarp(String str, String pattern){
	//主串长度
    int m = str.length();    
	//模式串的长度
	int n = pattern.length();    
	//计算模式串的hash值
    int patternCode = hash(pattern);
	//计算主串当中第一个和模式串等长的子串hash值
	int strCode = hash(str.substring(0, n));
	//用模式串的hash值和主串的局部hash值比较。
	//如果匹配，则进行精确比较；如果不匹配，计算主串中相邻子串的hash值。
	for(int i=0; i<m-n+1; i++){        
		if(strCode == patternCode && compareString(i, str, pattern)){           		return i;
		}
	//如果不是最后一轮，更新主串从i到i+n的hash值
        if(i<m-n){
            strCode = nextHash(str, strCode, i, n);
        }
	}  
	return -1;
}
private static int hash(String str){
	int hashcode = 0;
    //这里采用最简单的hashcode计算方式：
    //把a当做1，把b当中2，把c当中3.....然后按位相加
	for(int i = 0; i < str.length(); i++) {
        hashcode += str.charAt(i)-'a';
	}    
	return hashcode;
}
private static int nextHash(String str, int hash, int index, int n){
    hash -= str.charAt(index)-'a';
    hash += str.charAt(index+n)-'a';
	return hash;
}
private static boolean compareString(int i, String str, String pattern) {
    String strSub = str.substring(i, i+pattern.length());    
	return strSub.equals(pattern);
}
public static void main(String[] args){
    String str = "aacdesadsdfer";
    String pattern = "adsd";
    System.out.println("第一次出现的位置:"+rabinKarp(str, pattern));}

时间复杂度为O(n)。如果冲突太多的话，RK算法会退化为BF算法。

尽量减少比较次数的BM算法

Bob Boyer 和 JStrother Moore 发明。

BF算法中有许多无谓的比较，BM算法是对BF算法的改进。借助“坏字符规则”和“好后缀规则”，在每一轮比较是，让模式串尽可能多地右移，减少比较次数。

坏字符规则

坏字符是指模式串和子串当中不匹配的字符。

BM算法的检测顺序相反，是从字符串最右侧向最左侧检测，反向检测的好处稍后会提到。

当检测到第一个坏字符之后，并不需要让模式串一位一位地向后移动和比较，因为：只有模式串坏字符对齐的位置也是字符T的情况下，两者才有匹配的可能。所以遇到坏字符T后，在模式串中向前找，直接把模式串当中的字符T和主串的坏字符对齐，进行下一轮的比较。

坏字符的位置越靠右，下一轮模式串的挪动跨度就可能越长，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。

接下来，我们继续逐个字符比较，直到又遇到一个坏字符，按照上面的方式，找到模式串中相同的字符，与坏字符对齐后进行下一轮比较。

如果坏字符在模式串中不存在，直接把模式串挪到主串坏字符的下一位。

按照以上规则，已经能比较有效地找出下标了，代码如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//在模式串中，查找index下标之前的字符是否和坏字符匹配
private static int findCharacter(String pattern,char badCharacter,int index){
	for(int i = index-1;i>=0;i--) {
		if(pattern.charAt(i)==badCharacter) {
			return i;
		}
	}
	//模式串不存在该字符，返回-1
	return -1;
}
public static int boyerMoore(String str,String pattern){
	int strLength = str.length();
	int patternLength = pattern.length();
	//模式串的起始位置
	int start=0;
	while(start<=strLength-patternLength){
		int i;
		//从后向前，逐个字符比较
		for(i=patternLength-1;i>=0;i--){
			if(str.charAt(start+i)!=pattern.charAt(i))
				//发现坏字符，跳出比较，i记录了坏字符的位置
				break;
		}
		if(i<0){
			//匹配成功，返回第一次匹配的下标位置
			return start;
		}
		//寻找坏字符在模式串中的对应
		int charIndex = findCharacter(pattern,str.charAt(start+i),i);
		//计算坏字符产生的位移
		int bcOffset = charIndex>=0?i-charIndex:i+1;
		start += bcOffset;
	}
    return -1;

}
public static void main(String[]args){
	String str = "GTTATAGCTGGTAGCGGCGAA";
	String pattern = "GTAGCGGCG";
	int index = boyerMoore(str,pattern);
	System.out.println("首次出现位置："+index);
}

但对于某些情况仍有不足，因此需要用到好后缀规则。

好后缀规则

好后缀是指模式串和子串当中相匹配的后缀。

在下面的例子中，仅使用坏字符规则（G—A），模式串仅能向后移动一位。下面介绍好后缀的用法：

例如，主串： CTGGGCGAGCGGAA，模式串：GCGAGCG

在第一轮比较中，发现主串和模式串都有共同的后缀“GCG”，即“好后缀”。如果模式串其他位置也包含与“GCG”相同的片段，那么就可以移动模式串，使这一片段与好后缀对齐，进行下一轮的比较。

采用好后缀规则能够让模式串向后移动更多位，节省了更多无谓的比较。

如果模式串中并不存在其他与好后缀相同的片段，不能直接把模式串移到好后缀的后面，还需要判断一种特殊情况：模式串的前缀是否和好后缀的后缀相匹配，免得移过头了。

两种规则的结合：可以在每一轮字符比较之后，按照坏自读和好后缀规则分别计算相应的移动距离，选用更长的距离。代码有些复杂，暂时不涉足。

KMP算法

由D.E.Knuth、J.H.Morris和V.R.Pratt提出。与BM算法类似，试图减少无谓的字符串比较。为了实现这一点，KMP算法把专注点放在了已匹配的前缀上。

KMP算法和BF算法的“开局”是一样的，同样是把主串和模式串的首位对齐，从左到右对逐个字符进行比较。直到遇到一个坏字符时停下来。

例如，主串：GTGTGAGCTGGTGTGTGCFAA，模式串：GTGTGCF

为了有效利用已匹配的前缀 “GTGTG” ，可以发现，在前缀“GTGTG”当中，后三个字符“GTG”和前三位字符“GTG”是相同的。

在下一轮的比较时，只有把这两个相同的片段对齐，才有可能出现匹配。这两个字符串片段，分别叫做最长可匹配后缀子串和最长可匹配前缀子串。把模式串向后移动两位，继续从主串的坏字符A开始进行比较。这时，主串的A仍是坏字符，并且此时的匹配前缀缩短为GTG，最长可匹配前缀子串是G，右移模式串，使两个G对齐，继续从刚才主串的坏字符A开始进行比较

整体思路：在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。找两个子串的方法：在next数组中缓存。

next数组

next数组是一个一维整型数组，数组下标表示“已匹配前缀的下一个位置”，元素的值表示“最长可匹配的前缀子串的下一个位置”。对于上面的例子，next数组为：

i 0 1 2 3 4 5 6
next[i] 0 0 0 1 2 3 0
字符串前缀 无 G GT GTG GTGT GTGTG GTGTGC

可以通过已匹配前缀的下一个位置（坏字符位置）快速寻找到最长可匹配前缀的下一个位置，然后把这两个位置对齐。

当模式串的第一个字符就和主串不匹配时，并不存在已匹配前缀子串，对应next[0]=0。如果已匹配前缀是G、GT、GTGTGC，并不存在最长可匹配前缀子串，对应next[1]=next[2]=next[6]=0。GTG的最长可匹配前缀是G，对应next[3]=1。

生成next数组

由于已匹配前缀数组在主串和模式串当中是相同的，所以我们仅仅依据模式串，就足以生成next数组。最简单的方法是从最长的前缀子串开始，把每一种可能情况都做一次比较。假设模式串的长度是m，最大总比较次数是1+2+3+4+……+m-2 次，这种方法效率太低。

另外一种方法是动态规划：

  1. 初始状态：next[0]和next[1]的值是0，因为这时候不存在前缀子串；

  2. 状态转移方程：当模式串当中 pattern[j] = pattern[i-1]时，next[i] = next[i-1]+1;

    对于i=6，可以把计算“GTGTGC”最长可匹配前缀子串的问题，转化成计算“GTGC”最长可匹配前缀子串的问题。这样的问题转化，也就相当于把变量j回溯到了next[j]。

1. 对模式串预处理，生成next数组

2. 进入主循环，遍历主串

​ 2.1. 比较主串和模式串的字符

​ 2.2. 如果发现坏字符，查询next数组，得到匹配前缀所对应的最长可匹配前缀子串，移动模式串到对应位置

​ 2.3.如果当前字符匹配，继续循环

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// KMP算法主体逻辑。str是主串，pattern是模式串
public static int kmp(String str, String pattern) {
    //预处理，生成next数组
    int[] next = getNexts(pattern);
    int j = 0;
    //主循环，遍历主串字符
    for (int i = 0; i < str.length(); i++){
        while (j > 0 && str.charAt(i) != pattern.charAt(j)){
            //遇到坏字符时，查询next数组并改变模式串的起点
            j = next[j];        
		}
        if (str.charAt(i) == pattern.charAt(j)){
            j++;
        }
        if (j == pattern.length()){
            //匹配成功，返回下标
            return i - pattern.length()+ 1;
        }
    }
    return -1;
}
// 生成Next数组
private static int[] getNexts(String pattern) {
    int[] next = new int[pattern.length()];    
	int j = 0;
    for (int i=2; i<pattern.length(); i++){        
        while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {
            //从next[i+1]的求解回溯到 next[j]
            j = next[j];
        }
        if (pattern.charAt(j) == pattern.charAt(i-1)){
            j++;
        }
        next[i] = j;
    }
    return next;
}
public static void main(String[] args){
    String str = "ATGTGAGCTGGTGTGTGCFAA";
    String pattern = "GTGTGCF";
    int index = kmp(str, pattern);
    System.out.println("首次出现位置："+ index);
}

空间复杂度：O(m)

时间复杂度： O(m+n)

KMP没看懂，明天继续吧。

以上参考：小灰