数据结构与算法之美（三）
字符串匹配
BF算法
BF算法是最简单也是最暴力的一种方法，即模式串依次在主串的第i个位置开始进行比较，相同则继续比较，不同就移至下一位重新比较。
package algorithm.string_match;
/**
* @author EnochStar
* @title: BF
* @projectName basic_use
* @description: TODO
* @date 2021/11/8 11:56
*/
public class BF {
public boolean isMatching(String mainString,String sonString) {
if (mainString == null || sonString == null) {
return false;
}
for (int i = 0;i < mainString.length() - sonString.length() + 1;i++) {
for (int j = 0;j < sonString.length();j++) {
if (mainString.charAt(i + j) != sonString.charAt(j)) {
break;
}
if (j == sonString.length() - 1) return true;
}
}
return false;
}
}复制代码极端情况下时间复杂度为O（n*m）（如：主串”aaaaaaaaaa.....“ 子串”aaaaaab“），尽管时间复杂度很高，但他是最常用的字符串匹配算法。原因如下：
1、在大多数情况下，主串和子串的长度不会特别长，同时子串在中途遇到不能匹配的字符时，就停止匹配了，所以不会完全遍历子串
2、该算法实现简单，当出现bug时也容易发现并修正。
RK算法
其思路是利用哈希算法，求得主串下的所有与模式串相同长度的子串的哈希值，这样只要比较哈希值即可确认主串中是否存在子串。关键就在于求主串下所有子串的哈希值所消耗的时间。
由图可知h[i]与h[i-1]存在一定的关系。
用数学表达可知，h[i] = 26h[i - 1] - 26^m(s[i - 1] - 'a') + s[i + m - 1] - 'a'.
package algorithm.string_match;
import java.util.HashSet;
import java.util.Set;
/**
* @author EnochStar
* @title: RK
* @projectName basic_use
* @description: TODO
* @date 2021/11/8 14:17
*/
public class RK {
private Set<Long> set = new HashSet();
public boolean matching(String mainString,String sonString) {
int m = sonString.length();
initSonOfMainHash(mainString,m);
long base = initBase(sonString,m);
return set.contains(base);
}
private void initSonOfMainHash(String mainString,int m){
long base = initBase(mainString,m);
set.add(base);
for (int i = 1;i < mainString.length() - m + 1;i++) {
base = (long) (26 * base - Math.pow(26,m) * (mainString.charAt(i - 1) - 'a')
+ (mainString.charAt(i + m - 1) - 'a'));
set.add(base);
}
}
private long initBase(String s,int m) {
long base = 0;
for (int i = 0;i < m;i++) {
base += Math.pow(26,m - i - 1) * (s.charAt(i) - 'a');
}
return base;
}
}复制代码由关系表达式，只需要O(n)的时间复杂度即可求得主串下所有子串的哈希值，用set判断模式串的哈希值是否存在也只需要O(n)的时间复杂度，故该方法的时间复杂度为O(n)，但存在缺陷，如果模式串和主串的长度都非常的长，超过了数值的范围，那么这种方法就不可取了，这时候只能允许哈希冲突，当存在哈希值的时候再使用BK算法进行判断。
BM
package algorithm.string_match;
import java.util.Arrays;
/**
* @author EnochStar
* @title: BM
* @projectName basic_use
* @description: TODO
* @date 2021/11/9 14:58
*/
public class BM {
// 用于存储坏字符最后一次出现在模式串的位置
private int[] table = new int[256];
public int bm(char[] a,int n,char[] b,int m){
initTable(b,m);
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
initSuffixAndPrefix(b,m,suffix,prefix);
int i = 0;
while (i <= n - m) {
int j;
for (j = m - 1;j >= 0;j--) {
if (a[i + j] != b[j]) break;
}
if (j < 0) return i;
int moveBad =j - table[a[j + i]];
int y = 0;
if (j < m - 1) {
y = moveGood(j,m,prefix,suffix);
}
i = i + Math.max(y,moveBad);
}
return -1;
}
private int moveGood(int j,int m,boolean[] prefix,int[] suffix) {
int k = m - 1 - j;
if (suffix[k] != -1) {
return j - suffix[k] + 1;
}
for (int r = j + 2;r <= m - 1;r++) {
if (prefix[m - r]) return r;
}
return m;
}
private void initTable(char[] b,int m) {
Arrays.fill(table, -1);
for (int i = 0;i < m;i++) {
int ascii = (int)b[i];
table[ascii] = i;
}
}
private void initSuffixAndPrefix(char[] b,int m,int[] suffix,boolean[] prefix){
Arrays.fill(suffix,-1);
Arrays.fill(prefix,false);
for (int i = 0;i < m - 1;i++) {
int j = i;
int k = 0;
while (j >= 0 && b[j] == b[m - 1 - k]) {
--j;
k++;
suffix[k] = j + 1;
}
if (j == -1) prefix[k] = true;
}
}
}
作者：不二鑫
链接：https://juejin.cn/post/7028096997567496205