算法篇-字符串匹配算法

字符串匹配指的是一个字符串是否包含另一个字符串或者是求它匹配的下标

Brute-force 算法

暴力匹配算法最容易想到但是其复杂度也越高，其实质就是需要枚举所有的结果进行对比，时间复杂度O(m*n)

代码实现

public int match(String str1,String str2){
   for (int i = 0; i < str1.length(); i++) {
     	 //如果首字母相等则开始检测匹配
       if (str1.charAt(i)==str2.charAt(0)){
           int start = i;
           int index = 0;
           while (str1.charAt(start++)==str2.charAt(index++))
           if (index==str2.length())return i;
       }
   }
   return -1;
}

Rabin-Karp 算法

rk算法的思路和bf基本一致，但其比较采用的是hash来比较两个字符串，而不是bf的逐一比较，当出现hash一致时只是有可能匹配（也可能是哈希冲突），在用bf相同的方式比较是否匹配。时间复杂度O(m+n)

如果单纯使用hash这种方法比暴力查找还慢，因为计算散列值会涉及字符串中的每个字符。Rabin和Karp对上述方法进行了改进，发明了一种能够在常数时间内算出M个字符的子字符串散列值的方法。

1.哈希冲突怎么办？

当出现哈嘻冲突的时候依然视为匹配，进行逐一比较每个字符串的字符

2.当模式串的长度很长怎么办？

进行统一取模处理

代码实现

public class RabinKarp {
    
  public final static int d = 10;

  static void search(String pattern, String txt, int q) {
    int m = pattern.length();
    int n = txt.length();
    int i, j;
    int p = 0;
    int t = 0;
    int h = 1;
    for (i = 0; i < m - 1; i++) h = (h * d) % q;
    //计算模式串和主串的hash
    for (i = 0; i < m; i++) {
      p = (d * p + pattern.charAt(i)) % q;
      t = (d * t + txt.charAt(i)) % q;
    }
    // 查找匹配
    for (i = 0; i <= n - m; i++) {
      //如果hash相同则比较每个字符
      if (p == t) {
        for (j = 0; j < m; j++)if (txt.charAt(i + j) != pattern.charAt(j))break;
        //全部匹配成功
        if (j == m)System.out.println("匹配位置: " + (i + 1));
      }
	  //如果还存在可以匹配的长度，继续下移匹配
      if (i < n - m) {
        //计算hash
        t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q;
        if (t < 0)t = (t + q);
      }
    }
  }
}

Knuth-Morris-Pratt 算法

KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

KMP的核心思想

每次移动的是将模式串的公共前后缀中的前缀移动到后缀位置，公共前后缀取的是模式串当前索引左边字符串最长公共前后缀且长度小于模式串指针左边长度。

[注]：公共前后缀：字符串前缀和字符串后缀相同的子字符串。如BAB的公共前后缀就是BAB，ABFDAB的公共前后缀就是AB

图解

代码实现

class KMP_String_Matching {
    void KMPSearch(String pat, String txt){
        int M = pat.length();//模式串长度
        int N = txt.length();//主串长度
        int lps[] = new int[M];//模式串的公共前后缀
        int j = 0; // index for pat[]
        int i = 0; // index for txt[]
        //计算模式串的公共前后缀
        computeLPSArray(pat, M, lps);
        while (i < N) {
            //依次匹配每个字符
            if (pat.charAt(j) == txt.charAt(i)) {
                j++;i++;
            }
            //匹配成功
            if (j == M) {
                System.out.println("匹配的索引:" + (i - j));
                j = lps[j - 1];
            }
            // 本轮匹配不成功
            else if (i < N && pat.charAt(j) != txt.charAt(i)) {
                if (j != 0){//从公共前缀的位置移动到公共公共后缀位置
                    j = lps[j - 1];
                }else {
                    i = i + 1;//下移一位继续匹配
                }
            }
        }
    }
  	//计算模式串的公共前后缀长度
    void computeLPSArray(String pat, int M, int lps[]){
        // 前一个最长前缀后缀的长度
        int len = 0;
        int i = 1;
        lps[0] = 0; // lps[0] 总是 0
        // 循环计算 lps[i] 从 i = 1 到 M-1
        while (i < M) {
            //判断前缀和后缀最后(新)一个字符是否相等，
            //i和len其实指向的是基于上一轮公共前后缀的下一个字符下标
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;//相等则+1
                i++;
            }
            // 如果(pat[i] != pat[len])分为两种情况
            else {
                if (len != 0) {//当len!=0则直接取前一个
                    len = lps[len - 1];
                } else {//当len==0取0再移动后缀下标
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
}

Boyer-Moore算法

核心思想

当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征，加快了搜索的步骤。

特征

• BM算法在移动模式串的时候是从左到右，而进行比较的时候是从右到左的。
• 通过坏字符和好后缀两个规则来确定移动的位置，每次根据这两个规则来取能移动最大值。

坏字符规则（bad-character shift）

当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果”坏字符”不包含在模式串之中，则最右出现位置为 -1。坏字符针对的是文本串。

1、模式串中没有出现了文本串中的那个坏字符，将模式串直接整体对齐到这个字符的后方，继续比较。
2、模式串中有对应的坏字符时，让模式串中 最靠右 的对应字符与坏字符相对。

好后缀规则（good-suffix shift）

当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为 -1。好后缀针对的是模式串。

1、如果模式串中存在已经匹配成功的好后缀，则把目标串与好后缀对齐，然后从模式串的最尾元素开始往前匹配。
2、如果无法找到匹配好的后缀，找一个匹配的最长的前缀，让目标串与最长的前缀对齐（如果这个前缀存在的话）。模式串[m-s，m] = 模式串[0，s] 。
3、如果完全不存在和好后缀匹配的子串，则右移整个模式串。

代码实现

public class bm {

    static int NO_OF_CHARS = 256;

    static void badCharHeuristic(char[] str, int size, int badchar[]) {
        for (int i = 0; i < NO_OF_CHARS; i++) badchar[i] = -1;
        for (int i = 0; i < size; i++) badchar[str[i]] = i;
    }

    static void search(char txt[], char pat[]) {
        int m = pat.length;
        int n = txt.length;

        int badchar[] = new int[NO_OF_CHARS];

        badCharHeuristic(pat, m, badchar);

        int s = 0;
        while (s <= (n - m)) {
            int j = m - 1;
            while (j >= 0 && pat[j] == txt[s + j]) j--;
            if (j < 0) {
                System.out.println("Patterns occur at shift = " + s);
                s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
            } else s += Math.max(1, j - badchar[txt[s + j]]);
        }
    }
}

void preBmBc(char *x, int m, int bmBc[]) {
   int i;
 
   for (i = 0; i < ASIZE; ++i)
      bmBc[i] = m;
   for (i = 0; i < m - 1; ++i)
      bmBc[x[i]] = m - i - 1;
}
 
 
void suffixes(char *x, int m, int *suff) {
   int f, g, i;
 
   suff[m - 1] = m;
   g = m - 1;
   for (i = m - 2; i >= 0; --i) {
      if (i > g && suff[i + m - 1 - f] < i - g)
         suff[i] = suff[i + m - 1 - f];
      else {
         if (i < g)
            g = i;
         f = i;
         while (g >= 0 && x[g] == x[g + m - 1 - f])
            --g;
         suff[i] = f - g;
      }
   }
}
 
void preBmGs(char *x, int m, int bmGs[]) {
   int i, j, suff[XSIZE];
 
   suffixes(x, m, suff);
 
   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}
 
 
void BM(char *x, int m, char *y, int n) {
   int i, j, bmGs[XSIZE], bmBc[ASIZE];
 
   /* Preprocessing */
   preBmGs(x, m, bmGs);
   preBmBc(x, m, bmBc);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
      if (i < 0) {
         OUTPUT(j);
         j += bmGs[0];
      }
      else
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
   }
}

参考资料

算法学习：https://www.geeksforgeeks.org/
BM: https://igm.univ-mlv.fr//~lecroq/string/node14.html