高速字符串匹配算法

Question

我基本上是一些高速字符串匹配算法的基準，我遇到了一些。

1. 向後非確定性DAWG（向無環詞圖）由貢薩洛納瓦羅和馬修Raffinot 匹配算法。看到「 位並行方針後綴自動機：快速擴展字符串匹配 」

2. Horspool年代博耶 - 穆爾字符串 搜索算法的改進版本。請參見「字符串實用快速搜索」

3. 按住Shift鍵或用錯配

4. KMP

還有沒有其他更好的高速字符串匹配算法我可以嘗試的算法？

編輯：還有另外一個thread類似的線，它具有很好的參考太

Answer 1

您也可以嘗試

• Z Algorithm：在某些方面甚至整潔比KMP
• Aho Corasick：基於特里和最初用於fgrep
• Rabin Karp：基於哈希

Answer 2

就我所知，雙向字符串匹配是字符串匹配的最佳通用算法。它具有線性最壞情況的複雜度，使用恆定的空間，並且不會超出必要的數量。背後的理論非常好。

如果你知道你的用戶不是混蛋，那麼針對你的架構優化的天真的字符串匹配將贏得短的「針」，而Boyer-Moore變種將開始真正爲長「針」做次線性事情。然而，天真的字符串匹配有一個二次最壞的情況，Boyer-Moore可以檢查輸入中的所有字符。處理不匹配所需的額外表格實際上對雙向字符串匹配帶來了令人驚訝的嚴重損失。

Answer 3

import java.util.Scanner; 

public class StringMatch { 

static int temp,i=0,j=0; static boolean flag=true,matcher=false; 

    static String str=null,mstr=null;static char astr[],amstr[]; 

     static void getter(){ 
     Scanner sc = new Scanner(System.in); 
     str = sc.nextLine(); 
     //String str="today is Monday"; 
     astr=str.toCharArray(); 
     mstr = sc.nextLine(); 
     //String mstr="is"; 
     amstr=mstr.toCharArray(); 
    } 
    static void stringMatch(){ 
     while(i<astr.length){ 
      if(astr[i]==amstr[j]){ 
      while((j!=amstr.length)&&flag){temp=i; 
       if(astr[i]!=amstr[j]) {flag=false;matcher=false;} 
       else{matcher=true;} 
       i++;j++; 
       //System.out.println(i+"\t"+j); 
      }if(matcher==true)break;i=temp;}i++;j=0;flag=true; 

     } 
     if(matcher==true) {System.out.println("true");} 
     else {System.out.println("false");} 
    } 
    public static void main(String[] args) { 

    StringMatch.getter(); 
    StringMatch.stringMatch(); 

    } 
}