java - Java検索文字列(kmp)

Question

文字列bに文字列（aとしましょう）が何回出現するかを検索したいと思います。Knuth-Morris-Pratt Algorithm を実装することを考えましたが、組み込みの Java 関数を好みます。このような機能はありますか？私は何度も使用するので、できるだけ複雑度が低い関数にしたいと考えています。

Answer 1

KMP アルゴリズムは標準 Java ライブラリの一部ではありませんが、このような実装をオンラインで簡単に見つけることができます。

Answer 2

Java では、単純にメソッドを使用できますString.indexOf()。

KMP アルゴリズムは使用しません。短いストリングでは十分ですが、パフォーマンスが必要で大きなストリングを使用する場合は、適切な選択ではありません。

ただし、簡単な解決策が必要な場合は、次のとおりです。

int n = 0, i = 0;
while (i < str.length() 
       && (i = str.indexOf("al", i)) != -1) {
  ++n;
  ++i;
}
System.out.println("n: " + n);

部分文字列のすべての出現をカウントします。

Answer 3

これは私が行った非常に古いプロジェクトの一部です。インスピレーションには良いかもしれませんが、それが最速の方法かどうかはわかりません.

基本的に、Automaton 関数を使用してステート マシン テーブルを作成します。次に、数学関数を使用して発生を確認します。

Automaton Param : pattern は探しているパターンで、alpha はそのパターンのすべての文字です (例: pattern - aabba、alpha - ab)

フランスのコメントをお詫びします！

public Automaton(String pattern, char[] alpha){

    //declaration et initialisation
    _alpha = alpha;
    _pattern = pattern;
    int m = pattern.length();
    String Pqa = "";
    String Pk = "";

    //Initialisation du Map
    for(int map = 0; map < alpha.length ; map++){
        alphaMapc.put(alpha[map],alpha[map]);
        alphaMapNum.put(alpha[map],map);
    }

    tableau = new int[pattern.length()+1][alpha.length];

    // Algo d'apres le pseduo code et les notes
    for(int q=0 ; q <= m ; q++){            
        for( int j =0 ; j <  alpha.length ;  j++  ){
            Pqa = pattern.substring(0,q );
            Pqa += alpha[j];
            int k = Math.min(m+1, q+2);

            //Do while qui test Pq avec toutes le fins possibles
            do{
                k = k-1;
                Pk = pattern.substring(0, k);

            }while( k >0 && !(Pqa.endsWith(Pk)) );

            tableau[q][j] = k;
            System.out.print(k + " "); // TEST OUTPUT
        }
        System.out.println(); // TEST OUTPUT
    }



}

public int match(String string) {

    //Initialisation de letat et du compte
    int etat = 0;
    int compte = 0;

    for(int s = 0; s < string.length() ; s++){          
        char t = string.charAt(s);      

        //Acces en O(1)
        if(t == alphaMapc.get(t)) etat = tableau[etat][alphaMapNum.get(t)];

        //Si on atteint un etat final, on recommence a l'entree de la machine et on increment le compteur
        if(etat == 15){
            etat = 0;
            compte++;
        }
    }

    //Test
    System.out.println("Compte: " + compte);
    return compte;
}

それが役に立てば幸い！

よろしく、エルワルド