字符串匹配算法总结
面写过一篇字符串匹配算法,总共涉及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;
}