Java search String(kmp)

Question

I want to search how many occurrences of a string(lets say a) are in a string b. I thought of implementing Knuth-Morris-Pratt Algorithm, but I prefer a built in java function. Is there any function like this? I want the function to be as with the lowest Complexity as possible since I use it many times.

Answer 1

The KMP algorithm is not part of the standard Java library, but it's easy enough to find implementations online, like this one.

Answer 2

This is part of a very old project I did. Might be good for inspirating but not sure if it is the fastest way.

Basiclly you use the Automaton function to create a state machine table. Then, you use the math function to check the occurences!

Automaton Param : pattern is the pattern you're looking for and alpha are all the caracters in that pattern (ex : pattern - aabba, alpha - ab)

My appologies for the french comments!

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;
}

Hope it helps!

Regards, Erwald

Answer 3

In Java you can simply use the String.indexOf() method.

It do not use the KMP algorithm. For short string it is good enough, but if you need performance and you intend to use with large string then is not a good choice.

However if you want a simple solution, here it is:

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

it counts all the occurrences of the substring.