高速ストリングマッチングアルゴリズム

Question

私は基本的にいくつかの高速ストリングマッチングアルゴリズムをベンチマークしています。

1. 下位非決定的DAWG（有向非巡回単語グラフ）はGonzaloナバロとのMathieu Raffinotによって マッチングアルゴリズム。ボイヤー - ムーア文字列 検索アルゴリズムの

2. Horspoolの改良版：「高速拡張文字列 マッチング ビット並列サフィックスオートマトンへのアプローチ」を参照してください。不一致

3. KMP

とShiftキーを押しながらまたはアルゴリズム

「の文字列で実用的な高速検索」を参照してください。私は試すことができアルゴリズムに一致する他の優れた高速文字列はありますか？

編集：同様のライン内の別のthreadがあり、良いの参照を持って、あまりにも

Answer 1

また

• Z Algorithm試すことができますいくつかの方法でも、すっきりKMP
より
• Aho Corasick：トライベースともともとはfgrepに使用されました
• Rabin Karp：ハッシュベース

Answer 2

双方向の文字列のマッチングは、私の知る限り、文字列のマッチングのための最良の汎用アルゴリズムです。これは線形で最悪の場合の複雑さを持ち、一定のスペースを使い、必要以上にバックトラックしません。その背後にある理論はとてもいいです。

あなたのユーザーがジャークではないことがわかっている場合、アーキテクチャに最適化された素朴な文字列マッチングは短い "針"に勝ちますが、Boyer-Mooreの亜種は長い "針"に対して実際にサブラインのことをし始めます。しかし、素朴な文字列のマッチングは2次のワーストケースを持ち、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(); 

    } 
}