高速字符串匹配算法

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(); 

    } 
}