字符串搜索算法总结

因为在网上搜寻hash算法的知识，无意中又找到一些字符串搜索算法。 由于之前已经学习过一些搜索算法，觉得应该可以归为一类。因此就写一篇文章来记录下学习的过程。

问题：

在一长字符串中找出其是否包含某子字符串。

首先当然还是简单算法，通过遍历来检索所有的可能：

	public static int naiveSearch(String content, String sub) {
		for(int i = 0; i < (content.length() - sub.length() + 1); i++) {
			boolean found = true;
			for(int j = 0 ; j < sub.length(); j++) {
				if(content.charAt(i + j) != sub.charAt(j)) {
					found = false;
					break;
				}
			}
			
			if(found) return i;
		}
		
		return -1;
	}

时间复杂度为 Θ((n-m+1) m)

Rabin–Karp，即hash检索法：

	public static int rabinKarp(String content, String sub) {
		long hcontent = rshash(content.substring(0, sub.length()));
		long hsub = rshash(sub);
		
		for(int i = 0; i < (content.length() - sub.length()); i++) {
			//hcontent = rshash(content.substring(i, sub.length() + i));

			if(hsub == hcontent) {
				if(sub.equals(content.substring(i, i + sub.length()))) {
					return i;
				}
			}
			
			hcontent = newhash(content, hcontent, i + 1, sub.length());
		}
		
		return -1;
	}
	
	private static long rshash(String str)  
	{
	   int a = 63689;
	   long hash = 0;
	   
	   for(int i = 0; i < str.length(); i++)
	   {
	      hash += a * str.charAt(i);
	   } 
	   return hash;
	}
	
	private static long newhash(String str, long previous, int i, int length)  
	{
	   int a = 63689;
	   
	   long minHash = str.charAt(i - 1) * a;
	   
	   long plusHash = str.charAt(i + length - 1) * a;
	   
	   return (previous - minHash + plusHash);
	}

这个算法的核心思想是，通过hash值，我们可以一次匹配一整条字串，速度上要快很多。
关键： 选择这样一种hash算法，使得从前一个hash值到后一个hash值仅需要常量的步骤。

我这里实现的hash算法可以做到这点，但是有效性并不高，应该还有其他的hash算法可以更好了减少冲突的发生。

KMP算法
KMP算法说简单也不简单，说复杂也不复杂。只要你理解了它的核心思想，代码量其实非常少。可是想要解释它的思想，却也不是一件容易的事情。

考虑再三，还是觉得自己无法胜任这个解释工作，于是找了一篇自己认为解释KMP算法比较透彻的文章，翻译出来，看看大家有没有更哈的建议。

KMP algorithm
http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm

实例
为了解释该算法的细节，我们首先利用一个实例来把算法的步骤过一遍。在这个过程中的任意时间点，该算法的状态都由两个变量来决定， m和i。 m代表在S中，某个对于W（pattern）匹配的起始位置。 i代表在W中的当前正在进行匹配工作的位置。我们来描述一下当算法开始时的状态：
             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

我们首先从0位开始匹配W和S中平行的字符串，如果匹配，则前进到下一位。然而当我们到第四步的时候，我们发现S[3]是空格而W[3]=‘D’，出现了第一个不匹配。在传统的模式匹配算法中，接下来我们应该从S[1]的位置重新开始匹配。然而，如果我们仔细观察，在S的0到3位中（也就是我们刚刚进行过匹配成功的位），除了0位，其它都没有‘A‘出现过。而假设某字符串中有和W匹配的子串，那么这个子串必须是以’A‘开头的。因此，我们可以确定，S的0到3位中，都不可能存在这样的子串，于是我们决定从S的4位中重新找起。也就是说，m=4， i=0.

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456


此时，我们获得了一个几乎匹配的“ABCDAB”，然后在W[6](S[10])这个位置上，我们又出现了一个不匹配。于是，我们应该继续扩大m的值去寻找下一个可能的匹配。那么m的下一个值应该设置为多少呢？

整个算法的核心就在于此，我们可以从不匹配的位置开始，即m=10，然后这并不是一个正确的选择，我们发先在S的4到10位中，第8位也是‘A’。因此，如果我们从第十位开始继续找起的话，有可能就错过了某个匹配。

S中第八位的‘A’和第九位的‘B’，分别跟W的第0第1位相匹配。KMP算法对此的处理是，新的m=8（即首位匹配的值），新的i=2（因为前两位根据统计，已经是匹配好的了）。然后我们从S的m+i开始匹配W的i位。

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

跟第一步类似，我们在i=2就出错了，下一步我们应该跳转到哪里呢？当然是m=11，i=0：

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

此时，我们又在m=17的位置上出错了，根据第二步的解释，我们这次跳到m=15而i=2：

             1         2 
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

找到该模式，算法结束，返回m的值15.

部分匹配表
如果我们刚才的分析那样，整个匹配算法的核心就在于，当某次匹配过程出现不匹配的值时，如何寻找下一个做匹配的位置(这里的位置包括两个概念，即起始位置和我们应该从哪个值开始做匹配)。这样的值当然是越大越好，因为选择的下一个匹配位置越大，我们跳过的值就越多，整个算法就越快。

如果单看我们之前的分析，好像这个确定下一个匹配位置的工作关系到S和W两张表。其实不是这样的，我们只需要对W进行一个预处理，就可以做到这点。

还是来看，当W是“ABCDABD”这样一个字串时。我们会发现除了起始位置是‘A’以外，4位的值也是‘A’，那么如果我们在某次匹配时，匹配到了W的第4位，那么下一次做匹配查找时，就应当从W第4位对应的那个字符开始：
m     123456
S ... ABCDAX...
W     ABCDABD
i     0123456
因为我们已经知道S[5]和W[4]是匹配的了，那么其实就不需要再匹配一次了。因此匹配的起始位置是m=5，但是应当从i=1那里开始进行匹配。

如果是这样的一个情况呢？
m     1234567
S ... ABCDABX..
W     ABCDABD
i     0123456
同样的道理，匹配的起始位置依然是m=5，但是应当从i=2开始匹配。

下面给出求出当从任一位出现不匹配是，应该从哪里开始从新匹配的算法：

	private static void next(char[] input, int[] table) {
		int pos = 2;
		int cnd = 0;
		
		table[0] = -1;
		table[1] = 0;
		
		while(pos < input.length) {
			if(input[pos - 1] == input[cnd]) {
				table[pos] = cnd + 1;
				pos++;
				cnd++;
			} else if(cnd > 0) {
				cnd = table[cnd];
			} else {
				table[pos] = 0;
				pos++;
			}
		}
	}

既然已经得到了这样一个表，那么写出整个KMP算法也不是什么难事了：

	private static void next(char[] input, int[] table) {
		int pos = 2;
		int cnd = 0;
		
		table[0] = -1;
		table[1] = 0;
		
		while(pos < input.length) {
			if(input[pos - 1] == input[cnd]) {
				table[pos] = cnd + 1;
				pos++;
				cnd++;
			} else if(cnd > 0) {
				cnd = table[cnd];
			} else {
				table[pos] = 0;
				pos++;
			}
		}
	}

最后两个算法分别是BM算法和有限自动机算法。昨天我花了一天的时间研究BM算法，对算法的本质有了一定的了解，但是对于如何编码还是有点困惑。

决定把这两个算法先放一下，在字符搜索算法上停留的时间有点长。还是等以后再继续学习。