Programa Java para implementar el algoritmo de búsqueda de strings para tamaños de texto cortos

Ejemplos:

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

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

En este programa, un texto y un patrón se dan como entrada y se busca un patrón en el texto, y obtenemos todas las instancias del patrón como salida.

Algoritmo:

• Tome texto y patrón como entrada.
• Ejecute un bucle for externo desde 0 hasta la longitud de la longitud del texto del patrón.
• Ejecute un ciclo interno desde 0 hasta la longitud del patrón.
• A través de esto, para cada carácter en cada índice del texto a partir de ese índice hasta índice+longitud del patrón, se busca el patrón en el texto.
• Si se encuentra el patrón, imprima el índice del bucle exterior en el que se encuentra ese patrón en el texto.
• De lo contrario, si no se encuentra el patrón, imprímalo.

A continuación se muestra la implementación del enfoque anterior:

// Java Program to Implement the String Search
// Algorithm for Short Text Sizes
  
import java.io.*;
  
class GFG {
    public static void main(String[] args)
    {
  
        String text = "geeksforgeeks is a coding website for geeks";
        String pattern = "geeks";
  
        // calling the method that is designed for
        // printing the instances of pattern
        // found in the text string
        stringMatch(text, pattern);
    }
    public static void stringMatch(String text, String pattern)
    {
  
        int len_t = text.length();
        int len_p = pattern.length();
  
        int k = 0, i = 0, j = 0;
  
        // loop to find out the position Of searched pattern
        for (i = 0; i <= (len_t - len_p); i++) {
  
            for (j = 0; j < len_p; j++)
            {
                if (text.charAt(i + j) != pattern.charAt(j))
                    break;
            }
            
            if (j == len_p)
            {
                k++;
                System.out.println("Pattern Found at Position: " + i);
            }
        }
        
        if (k == 0)
            System.out.println("No Match Found!");
        else
            System.out.println("Total Instances Found = " + k);
    }
}

Pattern Found at Position: 0
Pattern Found at Position: 8
Pattern Found at Position: 38
Total Instances Found = 3

Complejidad de tiempo en el peor de los casos:

Enfoque efectivo:

El algoritmo KMP es una forma efectiva de buscar un patrón dentro del texto. Durante el recorrido cuando se detecta una falta de coincidencia, algunos caracteres en el texto de la siguiente ventana ya son conocidos. Aprovechando esta ventaja, la complejidad del tiempo se reduce a O(n).

A continuación se muestra la implementación del enfoque efectivo:

// Java Program to Implement the String Search
// Algorithm for Short Text Sizes
  
class KMP_String_Matching {
    void KMPSearch(String pat, String txt)
    {
        int M = pat.length();
        int N = txt.length();
  
        // create lps[] that will hold the longest
        // prefix suffix values for pattern
        int lps[] = new int[M];
        int j = 0; // index for pat[]
  
        // Preprocess the pattern (calculate lps[]
        // array)
        computeLPSArray(pat, M, lps);
  
        int i = 0; // index for txt[]
        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                j++;
                i++;
            }
            if (j == M) {
                System.out.println("Found pattern "
                                   + "at index " + (i - j));
                j = lps[j - 1];
            }
  
            // mismatch after j matches
            else if (i < N
                     && pat.charAt(j) != txt.charAt(i)) {
                // Do not match lps[0..lps[j-1]] characters,
                // they will match anyway
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
    }
  
    void computeLPSArray(String pat, int M, int lps[])
    {
        // length of the previous longest prefix suffix
        int len = 0;
        int i = 1;
        lps[0] = 0; // lps[0] is always 0
  
        // the loop calculates lps[i] for i = 1 to M-1
        while (i < M) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            }
            else // (pat[i] != pat[len])
            {
                // This is tricky. Consider the example.
                // AAACAAAA and i = 7. The idea is similar
                // to search step.
                if (len != 0) {
                    len = lps[len - 1];
  
                    // Also, note that we do not increment
                    // i here
                }
                else // if (len == 0)
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
  
    // Driver program to test above function
    public static void main(String args[])
    {
        String text
            = "geeksforgeeks is a coding website for geeks";
        String pattern = "geeks";
  
        KMP_String_Matching effective
            = new KMP_String_Matching();
        effective.KMPSearch(pattern, text);
    }
}

Found pattern at index 0
Found pattern at index 8
Found pattern at index 38

Complejidad del tiempo: