面写过一篇字符串匹配算法，总共涉及BF算法，RK算法，BM算法，还有一种算法是KMP算法。这几种算法思想和代码我都认真阅读完之后，发现BM算法和KMP算法还是很难完全掌握。如果自己闭卷再做一次这两种算法，我心里还是没有底气。
这两种算法思想都比较复杂，没有简单的数学公式可以依赖，场景较多，并且代码实现较为巧妙，很难用代码直观的表达算法思想。
假设主串A=ggusfsabxabcabxabxyyy, 长度为n 模式串B=abxabcabxabx 长度为m
BF算法：对A进行遍历，截取12长度的子串，子串和B进行逐个字符比较，如果完全相同则找到。算法思想简单直观，容易理解。但是如果比较的字符串长度较长时，这种算法的效率较低，时间复杂度=O(m * (n - m)) = O(m * n)
RK算法：和BF算法思想类似，需要提前设计好一个散列函数，把B转换为整数，然后把A中截取的子串也转换为整数，这样子串和B就可以直接通过整数进行比较，时间复杂度立刻降为O(n-m)。但是要设计一个好的散列函数，匹配各种类型是比较困难的。
下面再介绍两种重量级的算法BM和KMP
两种算法都是在比较子串时，不用一个一个字符移动比较，而是移动较大的位置，提高比较的效率。
BM算法
坏字符规则：模式串B与主串的子串C，B从后往前逐字符与C比较，如果遇到不相等的字符则记为坏字符。遇到坏字符处理方式：B继续从后往前对比寻找最近与坏字符相等的字符，如果找到则移动到对应位置；如果没有找到，则跨越整个模式串。从后往前找到相同字符，还分两种情况找到的字符可能在坏字符位置的前面，也有可能在后面。所以使用坏字符规则，移动的距离可能为负数，这个时候就需要另外一种规则好后缀规则。
好后缀规则：模式串B与主串对比遇到坏字符时，有一部分已经匹配好，这部分就叫做好后缀。B继续从后往前查询，如果还存在好后缀这样的子串，则移动到相应位置。如果不存在，就匹配好后缀最长的后缀子串，如果都无法匹配就跨越整个模式串。
最后每次从坏字符规则和好后缀规则中，获取较大移动位置的那个值，移动相应距离即可。
KMP算法: 模式串B与主串逐个字符对比，相同则一直往下比较。如果遇到不相等的字符，前面已经匹配好的字符串则为好前缀C。从好前缀中获取最大匹配好前缀子串的坐标，比较其后一个字符是否和坏字符相等，不相等继续直到循环终止。
BM算法如下:
/**
*
* @param a 主串
* @param n 主串长度
* @param b 模式串
* @param m 模式串长度
* @return
*/
public int bm2(char[] a, int n, char[] b, int m)
{
int[] bc = new int[SIZE];
generateBC(b,m,bc);
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
generateGS(b,m,suffix,prefix);
int i = 0;// j表示主串与模式串匹配的第一个字符
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 x = j - bc[a[i+j]];
int y = 0;
if ( j < m-1){
y = moveByGS(j,m,suffix,prefix);
}
i = i + Math.max(x,y);
}
return -1;
}
private void generateBC(char[] b,int m, int[] bc){
for (int i = 0; i < SIZE; ++i){
bc[i] = -1;
}
for (int i = 0; i < m; ++i){
int ascii = (int)b[i];
bc[ascii] = i; // 如果ascii相同只需要存储 bc[ascii] = 最后一个
}
}
/**
*
* @param b = 模式串
* @param m = 表示长度
* @param suffix = 数组
* @param prefix
*/
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix)
{
for (int i = 0; i < m ; ++i){ //初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i){ // b[0,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;
}
}
/**
*
* @param j 表示坏字符对应模式串中的字符下标
* @param m 模式串长度
* @param suffix
* @param prefix
* @return
*/
private int moveByGS(int j,int m,int[] suffix, boolean[] prefix)
{
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] == true) return r;
}
return m;
}
KMP算法如下：
/**
* KMP算法
* @param a
* @param n
* @param b
* @param m
* @return
*/
public static int kmp(char[] a, int n, char[] b, int m)
{
int[] next = getNexts(b,m);//获取模式子串的最长前缀匹配子串的下表
int j = 0;
for (int i = 0; i < n; ++i){
while (j>0&&a[i]!=b[j]){//模式串和主串不等，模式串对应下表为j, 匹配的前缀为最后下标为j-1, 获取j-1的最大匹配前缀，比较 前缀+1 和 坏字符是否相同即可
j = next[j-1]+1;
}
if (a[i] == b[j]){//如果主串和模式串一样
++j;
}
if (j == m) return i - m + 1; // i是下标，m是长度 所有需要 i + 1 - m
}
return -1;
}
/**
* b表示模式串，m表示模式串的长度
* @param b
* @param m
* @return
*/
private static int[] getNexts(char[] b, int m)
{
int[] next = new int[m];
next[0] = -1; // 只有一个字符的前缀时，没有前缀
int k = -1;
for (int i = 1; i < m; ++i){ //遍历模式串 1 到 m-1
/**
* 如：模式串 ababacd.
* i从[1,6],k从[0,5]
* i = 1, k = -1 b[0] != b[1] => next[1] = -1
* i = 2, k = -1 b[0] = b[2] ++k => next[2] = 0
* i = 3, k = 0 b[1] = b[3] ++k => next[3] = 1
* i = 4, k = 1 b[2] = b[4] ++k => next[4] = 2
* i = 5, k = 2 b[3] != b[5] k = next[2] = 0, b[1] != b[5] k = next[0] = -1 => b[0] != b[5] , next[5] = -1
* i = 6, k = -1 b[0] != b[6] => next[6] = -1
*/
while (k != -1 && b[k+1] != b[i]){ // 如果 在前基础上下个字符不相等时，就会比较最长比较子串的 最长匹配字串，就是次长匹配子串，直到找到为止
k = next[k];
}
if (b[k+1] == b[i]){ // 思想next[2] = 0,表示 aba =》 a?ba? 只要 ？=？就会有 next[3] = 1
++k;
}
next[i] = k;
}
return next;
}
网友评论