算法之字符串匹配

---

编程语言提供的字符串查找函数，比如 Java 中的 indexOf()，Python 中的 find() 函数等，它们底层就是依赖字符串匹配算法。字符串匹配算法有很多种，比较简单暴力的是BF算法和RK算法。RK 算法是 BF 算法的改进，它巧妙借助了哈希算法，让匹配的效率有了很大的提升。

---

BF匹配算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。从名字可以看出，这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高。

先举个例子，在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。把主串的长度记作 n，模式串的长度记作 m。因为是在主串中查找模式串，所以 n>m。在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

在极端情况下，比如主串是“aaaaa…aaaaaa”（省略号表示有很多重复的字符 a），模式串是“aaaaab”。每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。

从上面的分析看出，BF匹配算法的时间复杂度很高，不过在实际开发中，他却比较常用，原因有以下两点：

1：每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。

2：朴素字符串匹配算法思想简单，代码实现也非常简单。 简单意味着不容易出错，如果有 bug 也容易暴露和修复。就是所谓的"Keep it Simple and Stupid"。

BF匹配算法代码实现：

package 匹配;

public class Bf {
	
	public static int bF(String a, String b) {
		int m = a.length();
		int n = b.length();
		int k = 0;
		// 将字符串变成字符数组比较两个字符串的字符
		char[] a1 = a.toCharArray();
		char[] b1 = b.toCharArray();
		// 总共比较m-n+1次
		for(int i=0;i<=m-n;i++) {
			k=0;
			// 每次比较n个字符
			for(int j=0;j<n;j++) {
				// 如果两个字符串中的字符相同，k加一
				if(a1[i+j]==b1[j]) {
					k++;
				}
				// 否则选取主串的下一个子串进行匹配
				else
					break;
			}
			if(k==n) {
				return i;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		int bF = bF("badef", "def");
		System.out.println(bF);
	}

}

RK匹配算法

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。它其实就是刚刚讲的 BF 算法的升级版。

在BF算法中，如果模式串长度为 m，主串长度为 n，那在主串中，就会有 n-m+1 个长度为 m 的子串，只需要暴力地对比这 n-m+1 个子串与模式串，就可以找出主串与模式串匹配的子串。但是，每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是 O(n*m)。对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。

RK算法的思路：通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。 如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。

RK算法代码实现如下：

package 匹配;

/**
 * RK字符串匹配代码实现
 * @author 15447
 *
 */

public class Rk {

	/**
	 * RK代码实现
	 * @param a
	 * @param b
	 * @return
	 */
	public static int rK(String a, String b) {
		int m = a.length(), n = b.length(), s, j;
		int[] hash = new int[m - n + 1];
		int[] table = new int[26];
		char[] a1 = a.toCharArray();
		char[] b1 = b.toCharArray();
		s = 1;
		// 将26的次方存储在一个表里
		for (j = 0; j < 26; j++) {
			table[j] = s;
			s *= 26;
		}
		// 计算出主串中各个子串的hash值
		for (int i = 0; i <= m - n; i++) {
			s = 0;
			for (j = 0; j < n; j++) {
				s += (a1[i + j] - 'a') * table[n - 1 - j];
			}
			hash[i] = s;
		}
		s = 0;
		// 将模式串的hash值计算出来
		for (j = 0; j < n; j++) {
			s += (b1[j] - 'a') * table[n - 1 - j];
		}
		// 比较各个子串和模式串的哈希值
		for (j = 0; j < m - n + 1; j++) {
			if (hash[j] == s) {
				return j;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		int rK = rK("badef", "def");
		System.out.println(rK);
	}
	
}

本文地址：https://blog.csdn.net/weixin_43894879/article/details/107891284