欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

算法之字符串匹配

程序员文章站 2022-03-26 17:44:23
编程语言提供的字符串查找函数,比如 Java 中的 indexOf(),Python 中的 find() 函数等,它们底层就是依赖字符串匹配算法。...


编程语言提供的字符串查找函数,比如 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