Implementación del algoritmo Rabin Karp usando Rolling Hash en Java

Hay tantos algoritmos de búsqueda de patrones para la string. El algoritmo KMP, el algoritmo Z, el algoritmo Rabin Karp, etc., estos algoritmos son la optimización del algoritmo de búsqueda de patrones ingenuos.

Algoritmo de búsqueda de patrones ingenuos:

Input   :  "AABACACAACAC"
Pattern :  "CAC"
Output  :  [4,9]

AABACACAACAC

Implementación:

// Java Program to Search for a Pattern String in the Input
// String returning the indices
 
// Importing input java classes
import java.io.*;
 
// Main class
public class GFG {
 
    // Method 1
    // To find pattern in the string
    static void search(String s, String pattern)
    {
        // Iterating over the string in which to be searched
        // for using the length() method
        for (int i = 0; i <= s.length() - pattern.length();
             ++i) {
 
            int check = 1;
 
            // Iterating over the string for which is to be
            // searched using the length() method
            for (int j = 0; j < pattern.length(); ++j) {
 
                // Now, checking the elements of pattern
                // with the given string using the charAt()
                // method
                if (s.charAt(i + j) != pattern.charAt(j)) {
 
                    // Setting check to zero as pattern is
                    // not detected here
                    check = 0;
 
                    // Break statement to hault
                    // execution of code
                    break;
                }
            }
 
            // Now if the check remains same as declared
            // then pattern is detected at least once
            if (check == 1) {
 
                // Printing the position(index) of the
                // pattern string in the input string
                System.out.print(i + " , ");
            }
        }
    }
 
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
        // Given custom input string
        String s = "AABACACAACAC";
 
        // Pattern to be looked after in
        // the above input string
        String pattern = "CAC";
 
        // Display message for interpreting the indices
        // ai where if the pattern exists
        System.out.print(
            "Pattern is found at the indices : ");
 
        // Calling the above search() method
        // in the main() method
        search(s, pattern);
    }
}

Pattern is found at the indices : 4 , 9 , 

Explicación de salida:

El algoritmo anterior para la búsqueda de patrones es el algoritmo básico, el peor, ya que la complejidad de tiempo promedio de este algoritmo es O (n × m), donde n es el patrón y m es la string dada. 

¿Cómo podemos reducir la complejidad de este algoritmo? 

Es posible con la ayuda de hacer hachís . El algoritmo Rabin Karp es uno de los algoritmos optimizados del algoritmo ingenuo que realiza la búsqueda pasando la string y buscando el patrón.

Ilustración: 

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

Procedimiento:

• Calcule el valor hash del patrón (al crear su propia función hash o ecuación para determinar un valor hash individual para cada carácter)
• Itere sobre la string, verifique el valor hash de cada substring generada del tamaño del patrón si coincide, verifique cada carácter del patrón, así como la String, si todo coincide, imprima el índice inicial de la string.
• Si no coincide, cambie al siguiente carácter omitiendo el primer carácter y agregando el valor hash del siguiente carácter que no calculamos el valor hash de la siguiente substring en la string solo deslizamos la ventana salteamos el primer carácter y agregamos el último carácter de la ventana calculando su valor hash, es decir, hash rodante.

 Implementación: 

Algoritmo de Rolling simple asumiendo el patrón de longitud 2

1. Inicializar temperatura = 4 (1 + 3)
2. Pasa el valor hash al siguiente elemento.
3. Iterar el bucle ‘i’ <= Array.length-pattern.length
4. Elimine el primer elemento de la variable temporal y agregue el siguiente elemento en la variable temporal. temp = temp-Array[i]+Array[i.pattern.length()]

// Java Program to illustrating Simple Rolling Hashing
 
// Importing input output classes
import java.io.*;
 
// Main class
class GFG {
 
    // Method 1
    // To search the pattern
    static void search(String S, String pattern)
    {
        // Declaring and initializing the hash values
        int hash1 = 0;
        int hash2 = 0;
 
        // Iterating over the pattern string to be matched
        // over
        for (int i = 0; i < pattern.length(); ++i) {
 
            // Storing the hash value of the pattern
            hash1 += pattern.charAt(i) - 'A';
 
            // Storing First hash value of the string
            hash2 += S.charAt(i) - 'A';
        }
 
        // Initially declaring with zero
        int j = 0;
 
        // Iterating over the pattern string to checkout
        // hash values
        for (int i = 0; i <= S.length() - pattern.length();
             ++i) {
 
            // Checking the hash value
            if (hash2 == hash1) {
 
                // Checking the value
                for (j = 0; j < pattern.length(); ++j) {
 
                    // Checking for detection of pattern in a
                    // pattern
                    if (pattern.charAt(j)
                        != S.charAt(i + j)) {
 
                        // Break statement to hault the
                        // execution of program as no
                        // pattern found
                        break;
                    }
                }
            }
 
            // If execution is not stopped means
            // pattern(sub-string) is present
 
            // So now simply detecting for one or more
            // occurrences inbetween pattern string using the
            // length() method
            if (j == pattern.length()) {
 
                // Pattern is detected so printing the index
                System.out.println(i);
            }
            // for last case of loop, have to check,
            // otherwise,
            // S.charAt(i + pattern.length()) below will
            // throw error
            if (i == S.length() - pattern.length())
                break;
 
            // Roll the hash value over the string detected
            hash2 = (int)((hash2) - (S.charAt(i) - 'A'))
                    + S.charAt(i + pattern.length()) - 'A';
        }
    }
 
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
 
        // Input string to be traversed
        String S = "AABAACAADAABAABA";
 
        // Pattern string to be checked
        String pattern = "AABA";
 
        // Calling the above search() method(Method1)
        // in the main() method
        search(S, pattern);
    }
}

0
9
12