字符串匹配这个功能,是非常常见的功能,比如"Hello"里是否包含"el"?
Java里用的是indexOf函数,其底层就是字符串匹配算法。主要分类如下:
BF算法
原理
BF 算法中的 BF 是 Brute Force 的缩写,中文叫作暴力匹配算法,也叫朴素匹配算法
这种算法的字符串匹配方式很“暴力”,当然也就会比较简单、好懂,但相应的性能也不高
比方说,我们在字符串 A 中查找字符串 B,那字符串 A 就是主串,字符串 B 就是模式串
我们在主串中,检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串,看有没有跟模式串匹配的
代码实现
package com.rubin.algorithm.charsetmatch;
/**
* 暴力匹配算法,也叫朴素匹配算法
* 我们每次都比对 m 个字符,要比对 n-m+1 次,所以,这种算法的最坏情况时间复杂度是 O(n*m)
* m:为匹配串长度
* n:为主串长度
*/
public class BruteForce {
public static boolean isMatch(String origin, String match) {
for (int i = 0; i <= (origin.length() - match.length()); i++) {
if (origin.substring(i, i + match.length()).equals(match)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(isMatch("ccaaac", "caaac"));
System.out.println(isMatch("ccaaac", "abc"));
}
}
RK算法
原理
RK 算法的全称叫 Rabin-Karp 算法,是由它的两位发明者 Rabin 和 Karp 的名字来命名的
每次检查主串与子串是否匹配,需要依次比对每个字符,所以 BF 算法的时间复杂度就比较高,是O(n*m)。我们对朴素的字符串匹配算法稍加改造,引入哈希算法,时间复杂度立刻就会降低
RK 算法的思路是这样的:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这里先不考虑哈希冲突的问题)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模式串和子串比较的效率就提高了
代码实现
package com.rubin.algorithm.charsetmatch;
/**
* Rabin-Karp 算法
*
* RK 算法的思路是这样的:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式
* 串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串和模式串匹配了(这
* 里先不考虑哈希冲突的问题)。因为哈希值是一个数字,数字之间比较是否相等是非常快速的,所以模
* 式串和子串比较的效率就提高了
*
* T = O(m+n)
* m:为匹配串长度
* n:为主串长度
*
* 适用于匹配串类型不多的情况,比如:字母、数字或字母加数字的组合 62 (大小写字母+数字)
*/
public class RabinKarp {
public static boolean isMatch(String origin, String match) {
int matchhash= str2hash(match);
for (int i = 0; i <= (origin.length() - match.length()); i++) {
if (matchhash == str2hash(origin.substring(i, i + match.length()))) {
return true;
}
}
return false;
}
private static int str2hash(String str) {
int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash *= 26;
hash += (str.charAt(i) - 97);
}
return hash;
}
public static void main(String[] args) {
System.out.println(isMatch("ccaaac", "caaac"));
System.out.println(isMatch("ccaaac", "abc"));
}
}
BM算法
原理
BF 算法性能会退化的比较严重,而 RK 算法需要用到哈希算法,而设计一个可以应对各种类型字符的哈希算法并不简单
BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,滑动算法
在这个例子里,主串中的 c,在模式串中是不存在的,所以,模式串向后滑动的时候,只要 c 与模式串有重合,肯定无法匹配。所以,我们可以一次性把模式串往后多滑动几位,把模式串移动到 c 的后面
BM 算法,本质上其实就是在寻找这种规律。借助这种规律,在模式串与主串匹配的过程中,当模式串和主串某个字符不匹配的时候,能够跳过一些肯定不会匹配的情况,将模式串往后多滑动几位
BM 算法包含两部分,分别是坏字符规则(bad character rule)和好后缀规则(good suffix shift)
- 坏字符规则
BM 算法的匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的
我们从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符(主串中的字符)
字符 c 与模式串中的任何字符都不可能匹配。这个时候,我们可以将模式串直接往后滑动三位,将模式串滑动到 c 后面的位置,再从模式串的末尾字符开始比较
坏字符 a 在模式串中是存在的,模式串中下标是 0 的位置也是字符 a。这种情况下,我们可以将模式串往后滑动两位,让两个 a 上下对齐,然后再从模式串的末尾字符开始,重新匹配
当发生不匹配的时候,我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在,我们把这个坏字符在模式串中的下标记作 xi。如果不存在,我们把 xi 记作 -1。那模式串往后移动的位数就等于 (下标,都是字符在模式串的下标)
第一次移动3位
c在模式串中不存在,所以 xi = -1,移动位数 n = 2 - (-1) = 3
第二次移动2位
a在模式串中存在,所以 xi = 0,移动位数 n = 2 - 0 = 2
- 好后缀规则

我们把已经匹配的我们拿它在模式串中查找,如果找到了另一个跟{u}相匹配的子串{u},那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置

如果在模式串中找不到另一个等于{u}的子串,我们就直接将模式串,滑动到主串中{u}的后面,因为之前的任何一次往后滑动,都没有匹配主串中{u}的情况

过度滑动情况:

当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候,并且重合的部分相等的时候,就有可能会存在完全匹配的情况
所以,针对这种情况,我们不仅要看好后缀在模式串中,是否有另一个匹配的子串,我们还要考察好后缀的后缀子串(c),是否存在跟模式串的前缀子串(c)匹配的
如何选择坏字符和好后缀:我们可以分别计算好后缀和坏字符往后滑动的位数,然后取两个数中最大的,作为模式串往后滑动的位数
代码实现
坏字符:
如果我们拿坏字符,在模式串中顺序遍历查找,这样就会比较低效
可以采用散列表,我们可以用一个256数组,来记录每个字符在模式串中的位置,数组下标可以直接对应字符的ASCII码值,数组的值为字符在模式串中的位置,没有的记为-1
bc[97]=a
bc[98]=b
bc[100]=d
有重复的字母以后面的位置为准
package com.rubin.algorithm.charsetmatch;
/**
* BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,滑动算法.
* 我们本例只讲解坏字符算法
*
* T = O(N/M)
* n:主串长度
* m:模式串长度
*/
public class BoyerMoore {
private static final int[] BC = new int[256];
private static void generateBC(String match) {
// 这里只负责处理英文字母 不负责汉字 空字符的处理
char[] chars = match.toCharArray();
for (int i = 0; i < BC.length; i++) {
BC[i] = -1;
}
for (int i = 0; i < chars.length; i++) {
int ascii = chars[i];
BC[ascii] = i;
}
}
public static int isMatch(String origin, String match) {
generateBC(match);
char[] originChars = origin.toCharArray(),
matchChars = match.toCharArray();
int m = originChars.length, n = matchChars.length;
int i = 0;
while (i <= (m - n)) {
int j;
for (j = n - 1; j >= 0; j--) {
if (matchChars[j] != originChars[i + j]) {
break;
}
}
if (j < 0) {
return i;
}
i = i + (j - BC[originChars[i + j]]);
}
return -1;
}
public static void main(String[] args) {
System.out.println(isMatch("ccaaac", "caaac"));
System.out.println(isMatch("ccaaac", "abc"));
}
}
应用
BM算法比较高效,在实际开发中,特别是一些文本编辑器中,用于实现查找字符串功能
Trie树
原理
Trie 树,也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题
比如:有 6 个字符串,它们分别是:how,hi,her,hello,so,see,我们可以将这六个字符串组成Trie树结构
Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起
其中,根节点不包含任何信息。每个节点表示一个字符串中的字符,从根节点到红色节点的一条路径表示一个字符串(红色节点为叶子节点)
Trie树的插入

Trie树的查找
当我们在 Trie 树中查找一个字符串的时候,比如查找字符串“her”,那我们将要查找的字符串分割成单个的字符 h,e,r,然后从 Trie 树的根节点开始匹配。如图所示,绿色的路径就是在 Trie 树中匹配的路径
Trie 树是一个多叉树
我们通过一个下标与字符一一映射的数组,来存储子节点的指针
假设我们的字符串中只有从 a 到 z 这 26 个小写字母,我们在数组中下标为 0 的位置,存储指向子节点a的指针,下标为 1 的位置存储指向子节点 b 的指针,以此类推,下标为 25 的位置,存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在,我们就在对应的下标的位置存储 null
当我们在 Trie 树中查找字符串的时候,我们就可以通过字符的 ASCII 码减去“a”的 ASCII 码,迅速找到匹配的子节点的指针。比如,d 的 ASCII 码减去 a 的 ASCII 码就是 3,那子节点 d 的指针就存储在数组中下标为 3 的位置中
代码实现
package com.rubin.algorithm.charsetmatch;
/**
* Trie 树,也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题
* 本示例只处理a-z26个英文字母
*
* 如果要在一组字符串中,频繁地查询某些字符串,用 Trie 树会非常高效。构建 Trie 树的过程,需要扫
* 描所有的字符串,时间复杂度是 O(n)(n 表示所有字符串的长度和)。但是一旦构建成功之后,后续的
* 查询操作会非常高效。每次查询时,如果要查询的字符串长度是 k,那我们只需要比对大约 k 个节点,
* 就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说,构建好 Trie 树后,在其中
* 查找字符串的时间复杂度是 O(k),k 表示要查找的字符串的长度
*/
public class TrieTree {
private TrieNode root;
public TrieTree() {
root = new TrieNode('/');
}
static class TrieNode {
char data;
TrieNode[] children;
boolean isLeaf;
public TrieNode(char data) {
this.data = data;
children = new TrieNode[26];
isLeaf = false;
}
}
public void insert(String text) {
char[] textChars = text.toCharArray();
TrieNode p = root;
for (int i = 0; i < textChars.length; i++) {
int j = textChars[i] - 97;
if (p.children[j] == null) {
p.children[j] = new TrieNode(textChars[i]);
}
p = p.children[j];
}
p.isLeaf = true;
}
public boolean isMatch(String pattern) {
char[] patternChars = pattern.toCharArray();
TrieNode p = root;
for (int i = 0; i < patternChars.length; i++) {
int j = patternChars[i] - 97;
if (p.children[j] == null) {
return false;
}
p = p.children[j];
}
if (p.isLeaf == false) {
return false;
}
return true;
}
public static void main(String[] args) {
TrieTree trieTree = new TrieTree();
trieTree.insert("hello");
trieTree.insert("her");
trieTree.insert("hi");
trieTree.insert("how");
trieTree.insert("see");
trieTree.insert("so");
System.out.println(trieTree.isMatch("ho"));
System.out.println(trieTree.isMatch("how"));
System.out.println(trieTree.isMatch("howw"));
}
}
典型应用
利用 Trie 树,实现搜索关键词的提示功能
以上就是本文的全部内容了。欢迎小伙伴们积极留言交流~~~
文章评论