子字符串查找算法_归纳及汇总

字符串的一种基本操作就是子字符串查找：给定一段长度为N的文本和一段长度为M的模式字符串，在文本中找到一个和该模式相符的字符串。

模式-> ABCDE
正文-> SJAHDJKS”ABCDE”QWIYUE

上文加引号处就是被搜索出来的结果。
相信这个大家肯定是经常遇到的吧，不管是使用　“CTRL+F”　搜索还是在一些搜索栏中搜索一段文字，将包含该文字的书籍输出中，我们都会遇到，所以在这里对子字符串的查找算法进行一个归纳及汇总。

暴力子字符串查找算法

这种算法是一种比较简单而使用广泛的暴力算法，在最坏的情况下运行时间与MN成正比，但是在许多的正常情况下，它的实际运行时间一般与M+N成正比（在不同情况下，与M+N成正比的概率越高，就越好）。

算法思路
将模式文本的首字母一个个的与文本进行比较，如果相同就比较模式文本的下一个字母，如果在N-M的循环中还没有找到，则表明不匹配，结束循环。这里N-M次循环是因为M为模板文本的长度，N为文本的长度，超过这个数值的话剩下的字符串长度肯定小于M的，就肯定不匹配。因此就不用比较了

代码实现

/**
	 * 暴力子字符串查找算法
	 * 利用两层循环
	 * 一个变量跟踪正文文本，一个变量跟踪模板文本
	 * 
	 * @param pat
	 *            模板文本
	 * @param txt
	 *            正文文本
	 * @return
	 */
	public static String search(String pat, String txt) {
		int M = pat.length();
		int N = txt.length();
		
		// 用j来跟踪模板文本
		int j = 0;
		
		// 用i来跟踪正文文本
		for(int i = 0; i < N - M; i++) {
			
			// 依次匹配，一个字符一个字符的匹配
			// 如果匹配成功，就返回i的值
			for(j = 0; j < M; j++) {
				if (txt.charAt(i+j) != pat.charAt(j)) {
					break;
				}
			}
			if (j == M) {
				return "找到匹配文本，索引位置为: " + i;
			}
		}
		return "未找到匹配文本, 正文文本长度为" + N;
	}

这一段代码只进行了一个简单的示例，根据需要可以对其进行一个优化，比如说在j的for循环中，就算是整个字符串都被匹配了，仍然后遍历后面的字符串，这就没有必要了。因此可以设置一个标志位，如果整个模板文本已经匹配成功的话就设置标志位为true,同时返回。

当然了，上面的这段代码是只进行一次字符串的重复匹配，就算一个正文文本中存在多个模板文本，也只会搜索出一个，因为搜索到一个之后就return了，根据自己的需要可以再进行算法的优化及更新，因为这篇博客只是一个算法的归纳及汇总，思路及逻辑最重要，就不涉及过多单一算法的优化了，下面介绍的算法类同。

可能出现的问题
例如模板字符串为: ABCD
正文字符串为: AAAAAAAAAAQWEYUQIWABCDISDYQIU
这种算法主要存在的问题就是，如果模板字符串存在一连串的A开头，那么对应的查找就会变得慢了。
总结一下：算法的匹配效率不恒定，正常情况下没问题，极端情况下可能会很慢

KMP子字符串查找算法

这个算法（俗称看毛片算法）需要对模式字符串进行预处理，这里就只归纳一下思路。

思路
KMP算法的基本思想是当出现不匹配时，就能知晓一部分文本的内容(因为匹配失败之前它们已经和模板文本匹配，除了第一次匹配就失败的)。我们就可以利用这些信息避免将指针回退到所有这些已知的字符之前。

例如：
模板文本为:BAAAAAAA
正文文本中又只存在A,B两个字符
党我们开始匹配的时候，如果已经匹配了模板文本中的5个字符，第6个匹配失败，当发现不匹配的字符时，可以指导文本中的前6个字符肯定是BAAAAB（前５个匹配，第６个失败），文本指针现在指向的是第六个字符B。在这个时候，我们就不用回退文本指针了，因为匹配的前４个正文文本字符都是Ａ，与模式的第一个字符不匹配，因此，就可以直接从当前位置开始下一次的循环判断 。

这个理起来有点乱，多熟悉一下就好了，简单理解就是如果匹配失败，而当前文本索引所在位置的字符又是模板文本的开头时，我们不必回退文本指针到第二个位置再依次判断了，而可以根据一个记录来确定我们回退到哪个位置，这在一定程度上减少了循环的次数，提升了效率。

而至于上面的回退方法，其实是利用了一个next数组来实现，通过这个数组我们就可以知道每次回退需要退到哪个位置。

next数组的求法：
将当前序号，例如5前面的4个字符截取出来，然后顺数3个和倒数3个进行比较，如果相同，n就等于3.如果不同就用顺数2个和倒数2个比较，直到为0。
例如： abcde，现在指到了e，那么我们就用abc与bcd比较，它们不相同，就再比较ab与cd，还是不同，就比较a与d。这样就可以得出一个关于n的数组了

Boyer-Moore字符串查找算法

这种算法一般只会检查文本字符串中的一部分字符，现在许多的文本编辑器都使用了这个算法，用以显著的降低字符串查找的响应时间。

思路
当可以在文本字符串中回退时，如果可以从右向左扫描模板字符串并将它和正文文本匹配，那么这种字符串查找算法的速度就会非常快。

例如：
在查找字符串BAABBAA时，如果匹配了第7个和第６个字符，但是在第５个字符处匹配失败，那么马上就可以将模板文本向右移动7个位置并继续检查文本中的第14个字符。这是因为部分匹配找到了XAA而X不是B,而这三个字符在模板文本中是唯一的

这种算法跟上面的KMP的实现类似，也需要一个记录重启位置的数组

Rabin-Karp指纹字符串查找算法

这是一种基于散列（也就是Hash）的字符串查找算法，它与暴力算法几乎一样简单但是运行时间与M+N成正比的概率极高。此外，这种算法还可以拓展到二维的模板文本和正文文本中，这让它更适合于图像处理。

我们需要计算模板文本的散列函数，然后用相同的散列函数计算文本中所有可能的M个字符的子字符串散列值并寻找匹配。如果找到了一个散列值和模板文本相同的子字符串，那么再继续验证两者是否匹配。
可以理解为将模板文本保存在一张散列表中，然后在文本的所有字符串中进行查找。但不需要为散列表预留任何空间，因为它只包含一个元素。

如果直接利用上面的这段描述来实现代码的话肯定是不行的，因为计算散列值将会涉及到字符串中的每个字符，成本肯定是比直接比较字符要高。而RK算法就是一种能够在常数时间内算出M个字符的子字符串散列值的方法(需要预处理)，　这样就得到了一种能够在实际应用中的运行时间为线性级别的字符串查找算法。

思路
长度为Ｍ的字符串对应着一个R进制的M位数，为了用一张大小为Ｑ的散列表来保存这种类型的键，需要一个能够将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，Q在这里为997,则散列值为 26535 % 997 = 613，然后计算文本中所有长度为5个数字的子字符串的散列值并寻找匹配。
31415 % 997
14159 % 997
41592 % 997
…..
最后当求到26535时，与模板文本匹配，因此就可以找到了

总结

根据不同的需要选择不同的算法和模式我觉得才是最重要的，这些算法只要能够理解原理，那么在以后用到的时候也能够很快的运用到项目中去，毕竟在很多非算法要求特别高的工程中很有可能用不到很优秀算法，久了不用肯定是会忘的，但是只要懂了思想，哪怕是忘了如何用代码实现，在使用时也可以很快的熟悉它。这也是我总结算法的一个原因吧，思想及原理最重要。