kadoufall's Site

字符串匹配

  • Aug 14, 2017 
String string = "2359023141526739921";    // T
String pattern = "31415";                 // S

Naive

  • 从头到尾扫描string，对于每一个偏移，依次扫描m个连续的字符看是否都相同
  • 偏移是从0到n-m，共有n-m+1次
  • 时间复杂度为O(m*(n-m+1)) 
    public static void naive(String string, String pattern) {
      int n = string.length();
      int m = pattern.length();
      for (int i = 0; i <= n - m; i++) {
          boolean equal = true;
          for (int j = 0; j < m; j++) {
              if (string.charAt(i + j) != pattern.charAt(j)) {
                  equal = false;
                  break;
              }
          }
          if (equal) {
              System.out.println("Pattern occurs with shift " + i);
          }
      }
}

Rabin-Karp算法

  • 该算法的思想是用十进制数来表示每个字符串。则对于pattern，可用p表示其相应的十进制数；对于string，可用 ts 表示偏移s处连续m个字符对应的十进制数。这样如果能在O(m)时间内计算p，在总时间O(n-m+1)内计算所有的 ts，就能在总时间O(n)内找到所有偏移s
  • 运用霍纳规则在O(m)时间内计算p， 
    p = P[m] + 10(P[m-1] + 10(P[m-2] + ... + 10(P[2] + P[1]) ...))
  • 同样可以在O(m)时间内计算 t0，而通过t0计算后续t只需要常数时间
    • 若m = 5、t[s] = 31415、T[s+5+1] = 2， 则 
      t[s+1] = 10(31415 - 3 * 10^4) +2 = 14152

      t[s+1] = 10(t[s] - T[s+1] * 10^(m-1)) + T[s + m +1]
  • 所以可以在总时间O(n-m+1)内计算所有的 ts，这里用n-m+1不用n-m是因为凸显m=n时继续单计算t[s]需要O(1)
  • 算法有个问题是没有考虑p和t[s]的值太大的问题，所以改进的算法是，计算这些值的时候进行取模运算， 
    t[s+1] = (d(t[s] - T[s+1] * h) + T[s + m + 1]) mod q  ,  h = d*(m-1) (mod q), d进制
  • 由于是取模运算，所以可能会出现相同值的伪命中情况，所以最坏的情况进行验证的时间为O(m*(n-m+1)) 
    t[s+1] = (10(7 - 3 * (10^4 % 13)))%13 +2%13 = 8
  • 理想的情况下假设只有c个值是有效偏移，则匹配时间为O((n-m+1) + cm) = O(n+m)
  • 代码实现： 
    rabinKarp("235902314152673992131415", "31415", 128, 6999997);
rabinKarp("nadsuifhksfygifh", "ifh", 128, 6999997);

public static void rabinKarp(String string, String pattern, int d, int q) {
      int n = string.length();
      int m = pattern.length();
      int h = (int) Math.pow(d, m - 1) % q;
      int p = 0;
      int t = 0;

      for (int i = 0; i < m; i++) {
          p = (d * p + pattern.charAt(i)) % q;
          t = (d * t + string.charAt(i)) % q;
      }

      for (int i = 0; i <= n - m; i++) {
          if (p == t) {
              boolean equal = true;
              for (int j = 0; j < m; j++) {
                  if (string.charAt(i + j) != pattern.charAt(j)) {
                      equal = false;
                      break;
                  }
              }
              if (equal) {
                  System.out.println("Pattern occurs with shift " + i);
              }
          }
          if (i < n - m) {
              t = (d * (t - h * string.charAt(i) % q + q) + string.charAt(i + m)) % q;
          }
      }
  }
Search