kmp - string java 8

Encontrar todas las subcadenas comunes de dos cadenas dadas

Question

Me he encontrado con una declaración de problemas para encontrar todas las subcadenas comunes entre las dos subcadenas dadas de tal manera que en todos los casos tenga que imprimir la subcadena más larga. La declaración del problema es la siguiente:

Escriba un programa para encontrar las subcadenas comunes entre las dos cadenas dadas. Sin embargo, no incluya subcadenas que estén contenidas dentro de subcadenas comunes más largas.

Por ejemplo, dadas las cadenas de entrada eatsleepnightxyz y eatsleepabcxyz , los resultados deben ser:

• eatsleep (debido a eatsleep nightxyz eatsleep abcxyz eatsleep nightxyz eatsleep abcxyz )
• xyz (debido a eatsleepnight xyz eatsleepabc xyz )
• a (debido a e a tsleepnightxyz eatsleep a bcxyz )
• t (debido a eatsleepnigh t xyz ea t sleepabcxyz )

Sin embargo, el conjunto de resultados no debe incluir e de e atsleepnightxyz eatsl e epabcxyz , porque ambos es ya están contenidos en el eatsleep mencionado anteriormente. Tampoco debe incluir eat , eat , ats , etc., ya que también están cubiertos por eatsleep .

En esto, no tiene que hacer uso de los métodos de utilidad de cadena como: contiene, indexOf, StringTokenizer, dividir y reemplazar.

Mi algoritmo es el siguiente: estoy empezando con fuerza bruta y cambiaré a una solución más optimizada cuando mejore mi comprensión básica.

 For String S1:
     Find all the substrings of S1 of all the lengths
     While doing so: Check if it is also a substring of 
     S2.

Intento averiguar la complejidad del tiempo de mi enfoque.

Deje que las dos cadenas dadas sean n1-String y n2-String

1. El número de subcadenas de S1 es claramente n1 (n1 + 1) / 2.
2. Pero tenemos que encontrar la longitud media de una subcadena de S1.
3. Digamos que es m. Encontraremos m por separado.
4. La complejidad del tiempo para comprobar si una m-String es una subcadena de una n-String es O (n * m).
5. Ahora, estamos comprobando que cada m-String sea una subcadena de S2, que es una n2-String.
6. Esto, como hemos visto anteriormente, es un algoritmo O (n ² m).
7. El tiempo requerido por el algoritmo general es entonces
8. Tn = (Número de subcadenas en S1) * (duración promedio de la subcadena para el procedimiento de comparación de caracteres)
9. Al realizar ciertos cálculos, llegué a la conclusión de que la complejidad del tiempo es O (n ³ m ² )
10. Ahora, nuestro trabajo es encontrar m en términos de n1.

Intenta encontrar m en términos de n1.

T _n = (n) (1) + (n-1) (2) + (n-2) (3) + ..... + (2) (n-1) + (1) (n)
donde T _n es la suma de longitudes de todas las subcadenas.

El promedio será la división de esta suma por el número total de subcadenas producidas.

Esto, simplemente es un problema de suma y división cuya solución es la siguiente O (n)

Por lo tanto...

El tiempo de ejecución de mi algoritmo es O (n ^ 5).

Con esto en mente escribí el siguiente código:

 package pack.common.substrings;

 import java.util.ArrayList;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;

 public class FindCommon2 {
    public static final Set<String> commonSubstrings = new      LinkedHashSet<String>();

 public static void main(String[] args) {
    printCommonSubstrings("neerajisgreat", "neerajisnotgreat");
    System.out.println(commonSubstrings);
}

 public static void printCommonSubstrings(String s1, String s2) {
    for (int i = 0; i < s1.length();) {
        List<String> list = new ArrayList<String>();
        for (int j = i; j < s1.length(); j++) {
            String subStr = s1.substring(i, j + 1);
            if (isSubstring(subStr, s2)) {
                list.add(subStr);
            }
        }
        if (!list.isEmpty()) {
            String s = list.get(list.size() - 1);
            commonSubstrings.add(s);
            i += s.length();
        }
    }
 }

 public static boolean isSubstring(String s1, String s2) {
    boolean isSubstring = true;
    int strLen = s2.length();
    int strToCheckLen = s1.length();
    if (strToCheckLen > strLen) {
        isSubstring = false;
    } else {
        for (int i = 0; i <= (strLen - strToCheckLen); i++) {
            int index = i;
            int startingIndex = i;
            for (int j = 0; j < strToCheckLen; j++) {
                if (!(s1.charAt(j) == s2.charAt(index))) {
                    break;
                } else {
                    index++;
                }
            }
            if ((index - startingIndex) < strToCheckLen) {
                isSubstring = false;
            } else {
                isSubstring = true;
                break;
            }
        }
    }
    return isSubstring;
 }
}

Explicación de mi código:

 printCommonSubstrings: Finds all the substrings of S1 and 
                        checks if it is also a substring of 
                        S2.
 isSubstring : As the name suggests, it checks if the given string 
               is a substring of the other string.

Problema: Dadas las entradas

  S1 = “neerajisgreat”;
  S2 = “neerajisnotgreat”
  S3 = “rajeatneerajisnotgreat”

En el caso de S1 y S2, la salida debería ser: neerajis y great pero en el caso de S1 y S3, la salida debería haber sido: neerajis , raj , great , eat , pero aún así neerajis y great como salida. Necesito resolver esto.

¿Cómo debo diseñar mi código?

Answer 1

Estaría mejor con un algoritmo adecuado para la tarea que con un enfoque de fuerza bruta. Wikipedia describe dos soluciones comunes al problema más largo de subcadenas comunes : suffix-tree y dynamic-programming .

La solución de programación dinámica toma tiempo O ( nm ) y espacio O ( nm ). Esto es más o menos una traducción de Java sencilla del pseudocódigo de Wikipedia para la subcadena común más larga:

public static Set<String> longestCommonSubstrings(String s, String t) {
    int[][] table = new int[s.length()][t.length()];
    int longest = 0;
    Set<String> result = new HashSet<>();

    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < t.length(); j++) {
            if (s.charAt(i) != t.charAt(j)) {
                continue;
            }

            table[i][j] = (i == 0 || j == 0) ? 1
                                             : 1 + table[i - 1][j - 1];
            if (table[i][j] > longest) {
                longest = table[i][j];
                result.clear();
            }
            if (table[i][j] == longest) {
                result.add(s.substring(i - longest + 1, i + 1));
            }
        }
    }
    return result;
}

Ahora, desea todas las subcadenas comunes, no solo las más largas. Puede mejorar este algoritmo para incluir resultados más cortos. Examinemos la tabla para las entradas de ejemplo eatsleepnightxyz y eatsleepabcxyz :

  e a t s l e e p a b c x y z
e 1 0 0 0 0 1 1 0 0 0 0 0 0 0
a 0 2 0 0 0 0 0 0 1 0 0 0 0 0
t 0 0 3 0 0 0 0 0 0 0 0 0 0 0
s 0 0 0 4 0 0 0 0 0 0 0 0 0 0
l 0 0 0 0 5 0 0 0 0 0 0 0 0 0
e 1 0 0 0 0 6 1 0 0 0 0 0 0 0
e 1 0 0 0 0 1 7 0 0 0 0 0 0 0
p 0 0 0 0 0 0 0 8 0 0 0 0 0 0
n 0 0 0 0 0 0 0 0 0 0 0 0 0 0
i 0 0 0 0 0 0 0 0 0 0 0 0 0 0
g 0 0 0 0 0 0 0 0 0 0 0 0 0 0
h 0 0 0 0 0 0 0 0 0 0 0 0 0 0
t 0 0 1 0 0 0 0 0 0 0 0 0 0 0
x 0 0 0 0 0 0 0 0 0 0 0 1 0 0
y 0 0 0 0 0 0 0 0 0 0 0 0 2 0
z 0 0 0 0 0 0 0 0 0 0 0 0 0 3

• El resultado de eatsleep es obvio: esa es la raya diagonal 12345678 en la parte superior izquierda.
• El resultado de xyz es la diagonal 123 en la parte inferior derecha.
• El resultado se indica con un 1 cerca de la parte superior (segunda fila, novena columna).
• El resultado de t está indicado por el 1 cerca de la parte inferior izquierda.

¿Qué pasa con los otros 1 s a la izquierda, arriba y junto a los 6 y 7 ? Esos no cuentan porque aparecen dentro del rectángulo formado por la diagonal 12345678 ; en otras palabras, ya están cubiertos por el eatsleep .

Recomiendo hacer una pasada haciendo nada más que construir la mesa. Luego, haga una segunda pasada, iterando hacia atrás desde la parte inferior derecha, para reunir el conjunto de resultados.

Answer 2

Por lo general, este tipo de coincidencia de subcadenas se realiza con la asistencia de una estructura de datos separada llamada Trie (se pronuncia try). La variante específica que mejor se adapta a este problema es un árbol de sufijos . Tu primer paso debería ser tomar tus entradas y construir un árbol de sufijos. Luego, deberá utilizar el árbol de sufijos para determinar la subcadena común más larga, lo que es un buen ejercicio.