¿Funciona la siguiente implementación para encontrar la subcadena común más larga dentro de dos cadenas?

Sí, este algoritmo funciona, pero es terrible. Es en todos los sentidos peor que el algoritmo ingenuo.

Dices que poner s2 en el mapa hash evita tener que atravesar s2, ¡pero eso no es cierto! ¡Tuviste que atravesar s2 para poner todos los elementos en el mapa hash! El algoritmo ingenuo también atraviesa s2 exactamente una vez (descontando el ciclo s1, que tienen ambos algoritmos), por lo que es el mismo, excepto que ahora ha agregado un mapa hash. Inicializar el mapa hash solo llevará muchas veces más tiempo que simplemente hacer el algoritmo simple (en C ++).

Puede inicializar el mapa hash con cada posible subcadena de s2. Eso haría que el tiempo de búsqueda para las subcadenas O (1), pero desafortunadamente significa que el tiempo de inicialización del mapa hash es O (n ^ 2). Se necesitaría un caso de uso muy extraño para que eso tenga sentido.

Lo más sencillo es recorrer s2 desde [0..s2.size () – s1.size ()]. Compruebe si s1 es una subcadena que comienza en cada carácter, asegurándose de renunciar al momento en que se encuentra la primera falta de coincidencia. Simple, limpio y más rápido que su algoritmo hash. Esta es la variante ingenua y funciona muy bien para todos los casos, excepto los muy tóxicos.

Un algoritmo más sofisticado trataría de evitar aquellos casos tóxicos donde s1 es largo y muy repetitivo, y donde s2 contiene muchas coincidencias. Trabajar bien en esta situación requiere algo mucho más sofisticado *, pero es tanto trabajo que incluso la biblioteca estándar std :: string :: find no molesta.

* Consideraría ejecutar algo como la compresión LZW en las cadenas y luego implementar el algoritmo en las cadenas comprimidas. Sin embargo, es tan difícil imaginar un caso de uso no estúpido que dudo que alguien se haya molestado alguna vez.

No veo por qué usarías un hashmap para hacer esto. Su algoritmo puede funcionar, pero no ha indicado qué es un “elemento”: ¿es el elemento un carácter individual o una subcadena?
En segundo lugar, supongo que desea excluir los espacios en blanco del partido. Mi pensamiento inicial sería que podría hacer esto con un simple doble for loop, como este:

paquete de cadena más larga común;

/ **
* *
* @author mdaconta
* /
public class LongestCommonSubstring {

/ **
* @param argumenta los argumentos de la línea de comando
* /
public static void main (String [] args)
{
tratar
{
if (args.length <2)
{
System.out.println (“USO: java longestcommonsubsting.LongestCommonSubstring “);
System.exit (1);
}

Cadena cadena1 = args [0];
Cadena string2 = args [1];

System.out.println (“cadena1 es:” + cadena1);
System.out.println (“string2 es:” + string2);

StringBuilder currentSubstring = null;
StringBuilder biggerSubstring = null;
para (int i = 0; i {
char c = string1.charAt (i);
if (Character.isWhitespace (c))
continuar;

para (int j = 0; j {
// ¿está c en la cadena2?
char c2 = string2.charAt (j);

si (c == c2)
{
currentSubstring = new StringBuilder ();
// partido
int indexString1 = i;
int indexString2 = j;

char origC = c;

// ahora mira cuán lejos coinciden
while (c == c2 &&! Character.isWhitespace (c) && indexString1 {
currentSubstring.append (c);
indexString1 ++; indexString2 ++;
c = string1.charAt (indexString1);
c2 = string2.charAt (indexString2);
}

System.out.println (“currentSubstring es:” + currentSubstring);
if (más grandeSubstring! = nulo)
{
if (currentSubstring.length ()> biggestSubstring.length ())
{
greatestSubstring = currentSubstring;
System.out.println (“greatestSubstring es:” + biggestSubstring);
}
}
más
greatestSubstring = currentSubstring;

// revertir
c = origC;
j = indexString2;
}
}
}
System.out.println (“La subcadena más grande es:” + más grandeSubstring);

} captura (t arrojable)
{
t.printStackTrace ();
}
}
}

Esto no ha sido probado exhaustivamente y es un enfoque de fuerza bruta; Sin embargo, parece más simple de lo que estaba intentando. Siempre trato de hacer lo más simple posible y luego determinar si necesito optimizarlo. ¡Los mejores deseos!

Los hashes no funcionan de esa manera. Los hashes se calculan a partir de toda la cadena y de manera no reversible. Por lo tanto, el hash de s [0] no guarda relación con el hash de s o de cualquier subcadena de s o de cualquier otra cadena.