5.3 子字符串查找

5.3.1 常见查找算法

  • 暴力算法
  • KMP算法
  • Boyer-Moore算法
  • Rabin-Karp算法

5.3.2 暴力子字符串查找

算法描述

  • 使用字符指针i跟踪文本,j跟踪模式,当首字母匹配后,i不在增加,只是j变化

实现

  1. public static int search(String pat, String txt){
  2.     int M = pat.length();
  3.     int N = txt.length();
  4.     for (int i = 0; i < N; i++){
  5.         int j;
  6.         for (j = 0; j < M; j++){
  7.             if (pat.charAt(j) != txt.charAt(i))
  8.                 break;
  9.         }
  10.         if (j == M) return i;//找到匹配
  11.     }
  12.     return N;//未找到匹配
  13. }

算法分析

  • 最坏情况:暴力算法需要~NM次字符比较

证明:最坏假设模式是AAAB,M=4,文本是AAAAAAAAAB,N=10,对于N-M+1=7个可能匹配位置,AAAB中每个字符都要和文本比对到B,为4次,攻M(N-M+1)=28次比较,一般M<<N,则成本~NM

  • 实际情况:暴力算法运行和N+M成正比

暴力算法改进(显式回退)

算法描述

  • 同样使用i,j跟踪模式和文本,但i始终增加,相当于初始算法的i+j指向已经匹配过的字符,若匹配失败,则i回退至本次匹配起始位置下一个字符,j指回模式开头
  1. public static int searchPlus(String pat, String txt){
  2.     int i, M = pat.length();
  3.     int j, N = txt.length();
  4.     for (i = 0, j = 0; i < N && j < M; i++){
  5.         if (pat.charAt(j) == txt.charAt(i)) j++;
  6.         else {i -= j; j = 0;}
  7.     }
  8.     if (j == M) return i-M;//找到匹配
  9.     else return N;//未找到
  10. }

算法5.6 KMP算法

算法5.7 Boyer-Moore算法

算法5.8 Rabin-Karp算法