第五章第三节子字符串查找

2017-06-29

× 文章目录

1. 5.3.2 暴力子字符串查找算法
2. 5.3.3 Knuth-Morris-Pratt子字符串查找算法
3. 5.3.4 Boyer-Moore字符串查找算法
4. 5.3.5 Rabin-Karp 指纹字符串查找算法
5. 总结

字符串的一种基本操作就是 子字符串查找 ：给定一段长度为N的文本和一个长度为M的模式（pattern）字符串，在文本中找到一个和该模式相符的子字符串。
解决该问题的大部分算法都可以很容易地扩展为 找出文本中所有和该模式相符的子字符串 、 统计该模式在文本中的出现次数 、 找出上下文（和该模式相符的子字符串周围的文字） 的算法。

5.3.2 暴力子字符串查找算法

暴力子字符串查找

public static int search(String pat, String txt) {
  int M = pat.length();
  int N = txt.length();
  for (int i = 0; i <= N - M; i++) {//i跟踪文本
    int j;                          //j跟踪模式
    for (j = 0; j < M; j++) {
      if (txt.charAt(i + j) != pat.charAt(j))
        break;
    if (j == M) return i;  //找到匹配
    }
    return N;              //未找到匹配
  }
}

图5.3.2

暴力子字符匹配算法的另一种实现（显式回退）:

public static int search (String pat, String txt) {
  int j, M = pat.length();
  int i, N = txt.length();
  for (i = 0, j = 0; i < N && j < M; i++) {   //i指文本中已经匹配过的字符序列的末端
    if (txt.charAt(i) == pat.charAt(j)) j++;
    else {                                   //如果i和j指向的字符不匹配了，那么需要回退这两个指针的值
      i -= j;
      j = 0;
    }
    if (j == M) return i - M;  //找到匹配
    else return N;             //未找到匹配
  }
}

5.3.3 Knuth-Morris-Pratt子字符串查找算法

图5.3.4

模式指针的回退

在KMP字字符串查找算法中，不会回退文本指针i，而是使用一个数组dfa[][]来 记录匹配失败时模式指针j应该回退多远 。

KMP查找算法

当i和j所指向的字符匹配失败时（从文本的i-j+1处开始检查模式的匹配情况），模式可能匹配的下一个位置应该从i-dfa[txt.charAt(i)][j]处开始。按照算法，从该位置开始的dfa[txt.charAt(i)][j]个字符和模式的前dfa[txt.charAt(i)][j]个字符应该相同，因此 无需回退指针i ，只需要将j设为dfa[txt.charAt(i)][j]并将i加1即可，这正是当i和j所指向的字符匹配时的行为。

public int search(String txt) { //模拟DFA处理文本txt时的操作
  int i, j, N = txt.length(), M = pat.length();
  for (i = 0, j = 0; i < N && j < M; i++)
    j = dfa[txt.charAt(i)][j];
  if (j == M) return i - M;    //找到匹配
  else        return N;        //未找到匹配
}

DFA模拟

dfa[][]数组定义的正是一个确定有限状态自动机（DFA）。

图5.3.6

图5.3.7

构造DFA

需要重新扫描的文本字符正是pat.charAt(1)到pat.charAt(j-1)之间，忽略首字母是因为模式需要右移一位，忽略最后一个字符是因为匹配失败。 对于每个可能匹配失败的位置都可以预先找到重启DFA的正确状态 。
DFA该如何处理下一个字符？例如，对于 ABABAC，要判断在j=5时匹配失败后DFA应该怎么做。通过DFA可以知道完全回退之后算法会扫描BABA并达到状态3，因此可以将dfa[][3]复制到dfa[][5]并将C所对应的元素的值设为6，因为pat.charAt(5)是C（匹配）。
计算中最后一个关键细节是，你可以观察到在处理dfa[][]的第j列时维护重启位置X很容易。因为X<j，所以可以有已经构造的DFA部分来完成这个任务——X的下一个值是dfa[pat.charAt(j)][X]。

KMP子字符串查找算法中DFA的构造。对于每个j：

将dfa[][X]复制到dfa[][j]（对于匹配失败的情况）；
将dfa[pat.charAt(j)][j]设为i+1（对于匹配成功的情况）；
更新X。

dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) { //计算dfa[][j]
  for (int c = 0; c < R; c++)
    dfa[c][j] = dfa[c][X];
  dfa[pat.charAt(j)][j] = j+1;
  X = dfa[pat.charAt(j)][X];
}

图5.3.9

算法5.6 Knuth-Morris-Pratt字符串查找算法：该算法实现的构造函数根据模式字符串构造了一个确定有限状态自动机，使用search()方法在给定文本字符串中查找模式字符串。

public class KMP {
  private String pat;
  private int[][] dfa;
  public KMP(String pat) {//由模式字符串构造DFA
    this.pat = pat;
    int M = pat.length();
    int R = 256;
    dfa = new int[R][M];
    dfa[pat.charAt(0)][0] = 1;
    for (int X = 0, j = 1; j < M; i++) { //计算`dfa[][j]`
      for (int c = 0; c < R; c++)
        dfa[c][j] = dfa[c][X];          //复制匹配失败情况下的值
      dfa[pat.charAt(j)][j] = j+1;      //设置匹配成功情况下的值
      X = dfa[pat.charAt(j)][X];        //更新重启状态
    }
  }
  public int search(String txt) { //模拟DFA处理文本txt时的操作
    int i, j, N = txt.length(), M = pat.length();
    for (i = 0, j = 0; i < N && j < M; i++)
      j = dfa[txt.charAt(i)][j];
    if (j == M) return i - M;    //找到匹配(到达模式字符串的结尾)
    else        return N;        //未找到匹配（到达文本字符串的结尾）
  }
  public static void main(String[] args) {
    String pat = args[0];
    String txt = args[1];
    KMP kmp = new KMP(pat);
    StdOut.println("text:   " + txt);
    int offset = kmp.search(txt);
    StdOut.println("pattern: ");
    for (int i = 0; i < offset; i++)
      Stdout.println(" ");
    StdOut.println(pat);
  }
}

命题5n

5.3.4 Boyer-Moore字符串查找算法

启发式的处理不匹配的字符

因为是从右向左与模式进行匹配，所以首先会比较模式字符串中的E和文本中的N（位置为5的字符）。因为N也出现在了模式字符串中，所以将模式字符串向右移动5个位置，将文本中的字符N和模式字符串中（最左侧）的N对齐。然后比较模式字符串最右侧的E和文本中的S（位置在第10个字符），匹配失败，因为S不在模式字符串中，所以可以将模式字符串向右移动6个位置。。。。

起点

使用数组right[]记录字母表中的每个字符在模式中出现的 最靠右 的地方。（如果字符在模式中不存在则表示为-1）。 这个值揭示了如果字符出现在文本中且在查找时造成了一次匹配失败，应该向右跳跃多远。

子字符串的查找

在计算玩right[]数组之后，我们用一个索引i在文本中 从左向右 移动，用另一个索引j在模式中 从右向左 移动。内循环会检查正文和模式字符串在位置i是否一致。如果从M-1到0的所有j，txt.charAt(i+j)都和pat.charAt(j)相等，那么就找到了一个匹配。而则匹配失败，会遇到以下三种情况：
- 如果造成匹配失败的字符 不包含 在模式字符串中，将模式字符串向右移动j+1个位置（即将i增加j+1）。
- 如果造成匹配失败的字符包含在模式字符串中，那就可以使用right[]数组来将模式字符串和文本对齐，使得该字符和它在模式字符串中出现的最右位置相匹配。
- 如果这种方式无法增大i，那就直接将i加1来保证模式字符串至少向右移动了一个位置。

算法5.7 Boyer-Moore字符串匹配算法（启发式地处理不匹配的字符）：构造函数根据模式字符串构造了一张每个字符在模式中出现的最右位置的表格。查找算法会 从右向左 扫描模式字符串，并在匹配失败时通过跳跃将文本中的字符和它在模式字符串中出现的 最右位置 对齐。

public class BoyerMoore {
  private int[] right;
  private String pat;
  BoyerMoore(String pat) { //计算跳跃表
    this.pat = pat;
    int M = pat.length();
    int R = 256;
    right = new int[R];
    for (int c = 0; c < R; c++)
      right[c] = -1;            //不包含在模式字符串中的字符的值为-1
    for (int j = 0; j < M; j++) //包含在模式字符串中的字符的值为它在其中出现的最右位置
      right[pat.charAt(j)] = j;
  }
  public int search(String txt){ //在txt中查找模式字符串
    int N = txt.length();
    int M = pat.length();
    int skip;
    for (int i = 0; i <= N - M; i += skip) { //模式字符串和文本在位置i匹配吗？
      skip = 0;
      for (int j = M - 1; j >= 0; j--) {
        if (pat.charAt(j) != txt.charAt(i + j)) {
          skip = j - right[txt.charAt(i + j)];
          if (skip < 1) skip = 1;
          break;
        }
      }
      if (skip == 0) return i;            //找到匹配  
    }
    return N;                             // 未找到匹配
  }
  public static void main(String[] args) {
    String pat = args[0];
    String txt = args[1];
    KMP kmp = new KMP(pat);
    StdOut.println("text:   " + txt);
    int offset = kmp.search(txt);
    StdOut.println("pattern: ");
    for (int i = 0; i < offset; i++)
      Stdout.println(" ");
    StdOut.println(pat);
  }    
}

5.3.5 Rabin-Karp 指纹字符串查找算法

基本思想

长度为M的字符串对应着一个R进制的M位数。为了用一张大小为Q的散列表来保存这种类型的键，需要一个能够将R进制的M位数转化为一个0到Q-1之间的int值散列函数。 除留余数法 是一个好选择：将该数除以Q并取余。

计算散列函数

采用 Horner方法 。如下代码，计算了用char值数组表示的R进制的M位数的散列函数，所需时间与M成正比。对于这个数中的每一位数字，将散列值乘以R，加上这个数字，除以Q并取余数。
1
2
3
4
5
6
private long hash(String key, int M) { //计算key[0..M-1]的散列值
long h = 0;
for (int j = 0; j < M; j++)
h = (R * h + key.charAt(j)) % Q;
return h;
}

实现

图5.3.16

图5.3.17

算法5.8 Rabin-Karp 指纹字符串查找算法：算法的基础是散列。它在构造函数中计算了模式字符串的散列值并在文本中查找该散列值的匹配。

public class RabinKarp {
  private String pat;           //模式字符串（仅拉斯维加斯算法需要）
  private long patHash;         //模式字符串的散列值
  private int M;                //模式字符串的长度
  private long Q;               //一个很大的素数
  private int R = 256;          //字母表的大小
  private long RM;              //R^(M - 1) % Q
  public RabinKarp(String pat) {
    this.pat = pat;             //保存模式字符串（仅拉斯维加斯算法需要）
    this.M = pat.length();
    Q = longRandomPrime();
    RM = 1;
    for (int i = 1; i <= M - 1; i++)  //计算R ^ (M - 1) % Q
      RM = (R * RM) % Q;              //用于减去第一个数字时的计算
    patHash = hash(pat, M);
  }
  public boolean cheak(int i){        //蒙特卡洛算法
    return true;                      //对于拉斯维加斯算法，检查模式与txt(i..i-M+1)的匹配
  }
  private long hash(String key, int M) { //计算key[0..M-1]的散列值
    long h = 0;
    for (int j = 0; j < M; j++)
      h = (R * h + key.charAt(j)) % Q;
      return h;
  }
  private int search(String txt) { //在文本中查找相等的散列值
    int N = txt.length();
    long txtHash = hash(txt, M);
    if (patHash == txtHash && check(0)) return 0;      //一开始就匹配成功
    for (int i = M; i < N; i++) { //减去第一个数字，加上最后一个数字，再次检查匹配
      txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
      txtHash = (txtHash * R + txt.charAt(i)) % Q;
      if (patHash == txtHash)
        if (check(i - M + 1)) return i - M + 1;    //找到匹配
    }
    return N;                                      //未找到匹配
  }    
}

命题5p

总结

表5.3.2