Algoritmo explicado:determine si dos cadenas tienen una subcadena en común

Declaración del problema:dadas dos cadenas, determine si tienen una subcadena en común.

Ejemplo:¿"hola mundo" y "mundo" tienen una subcadena en común? Sí, ambos tienen la subcadena "mundo".

Enfoque

¿Cuáles son todas las subcadenas de string?

La cadena "palabra" tiene cuatro caracteres. Contiene 10 subcadenas entre la longitud 1 y 4. Aquí están las 10 subcadenas:

A primera vista, puede parecer que necesitamos recorrer todas las subcadenas en una cadena y verificar si esa subcadena está contenida en la otra cadena. Pero podemos hacerlo mejor.

Primero, la declaración del problema solo pregunta si las dos cadenas tienen al menos una subcadena en común. No nos pide que devolvamos las subcadenas compartidas.

En segundo lugar, observe que los caracteres individuales son subcadenas. Todas las demás subcadenas se componen de estos caracteres únicos.

Por lo tanto, el problema puede reducirse a verificar si dos cadenas tienen un solo carácter en común.

Intento 1:bucle + cadena.Contiene()

Podemos recorrer los caracteres de string1 y verificar si string2 contiene ese carácter. Podemos salir inmediatamente al encontrar una coincidencia:

foreach char in string1:
   if string2.Contains(char):
      return true

return falseCode language: plaintext (plaintext)

Las cadenas son matrices de caracteres. String.Contains() recorre todos los caracteres de la matriz y devuelve verdadero si el carácter existe.

En otras palabras, es un bucle anidado. Esto es ineficiente. En el peor de los casos, recorre M veces los caracteres de string2, donde M es la longitud de string1. Es un algoritmo O(n^2).

Por ejemplo, digamos que nos dan "palabra" y "bla". Recorrería todos los caracteres de "blah" cuatro veces:

Intento 2:bucle + búsqueda

Podemos hacer que esto sea más eficiente guardando caracteres de una cadena en una búsqueda. Luego recorra la otra cadena y use la búsqueda para buscar una coincidencia.

hashset = {}
foreach char in string1:
    hashset.Add(char)

foreach char in string2:
    if hashset.Contains(char):
       return true

return falseCode language: plaintext (plaintext)

Hacer una búsqueda en un hashset es una operación O(1). Estamos recorriendo cada cadena exactamente una vez, haciendo de este un algoritmo O(n). Esta es una mejora de orden de magnitud sobre el algoritmo Attempt 1 O(n^2) en teoría. En la práctica, el uso de un hashset agrega costos generales. En cadenas cortas, en realidad será más lento que el algoritmo O(n^2). Mostraré una comparación de rendimiento al final de este artículo usando varios tamaños de entrada.

Casos de prueba

La siguiente prueba unitaria parametrizada tiene 6 casos de prueba, comenzando con una entrada no válida:

[DataRow("", "", false)]
[DataRow(null, null, false)]
[DataRow("aaa", "bbb", false)]
[DataRow("aaa", "AAA", false)]
[DataRow("aaa", "aAA", true)]
[DataRow("aAA", "aaa", true)]
[TestMethod]
public void HaveACommonSubstringTest(string s1, string s2, bool expected)
{
	//arrange and act
	var actual = Algorithm.HaveACommonSubstring(s1, s2);

	//assert
	Assert.AreEqual(expected, actual);
}
Code language: C# (cs)

Código

using System.Collections.Generic;
using System.Linq;

public class Algorithm
{
	public static bool HaveACommonSubstring(string s1, string s2)
	{
		if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2))
			return false;

		var set = new HashSet<char>(s1.Select(c => c));

		foreach(var c in s2)
		{
			if (set.Contains(c))
				return true;
		}

		return false;
	}
}
Code language: C# (cs)

Comparación de rendimiento entre los algoritmos O(n) y O(n^2) en la práctica

Esta es una prueba de rendimiento en el peor de los casos. En el peor de los casos, las dos cadenas no comparten un solo carácter, lo que significa que el algoritmo tiene que buscar cada carácter en ambas cadenas. Está probando cadenas con longitudes de 26 a 260 000.

public void PerformanceTest()
{
	int size = 1;

	StringBuilder sbS1 = new StringBuilder();
	for(char a = 'a'; a <= 'z'; a++)
	{
		sbS1.Append(new string(a, size));
	}

	StringBuilder sbS2 = new StringBuilder();
	for (char a = 'A'; a <= 'Z'; a++)
	{
		sbS2.Append(new string(a, size));
	}

	var s1 = sbS1.ToString();
	var s2 = sbS2.ToString();

	Stopwatch sw = new Stopwatch();
	sw.Start();
	Algorithm.LoopAndLookup(s1, s2);
	sw.Stop();
	Console.WriteLine($"O(n) elapsed={sw.ElapsedMilliseconds}");
	sw.Reset();

	sw.Start();
	Algorithm.LoopAndContains(s1, s2);
	sw.Stop();
	Console.WriteLine($"O(n^2) elapsed={sw.ElapsedMilliseconds}");
	sw.Reset();

}
Code language: C# (cs)

Estos son los resultados:

La sobrecarga de usar el hashset en el algoritmo O(n) agrega alrededor de 4 milisegundos. Esta es una constante.

El punto de interrupción en el que O(n) comienza a volverse más rápido que el algoritmo O(n^2) tiene una longitud aproximada de 13 000. Después de ese punto, el O(n^2) comienza a volverse significativamente más lento.

Este es un buen recordatorio de que el análisis Big-O no le brinda una imagen completa al comparar algoritmos. El análisis Big-O se trata de comparar las tasas de crecimiento de los algoritmos. En teoría, los algoritmos O(n) siempre deberían crecer más lentamente que los algoritmos O(n^2). En la práctica, puede haber una gran constante que el análisis Big-O ignora, y puede requerir una gran entrada para que el algoritmo teóricamente más rápido sea realmente más rápido.

La clave es conocer el tamaño de entrada potencial con el que está tratando. Si sabe que está tratando con entradas pequeñas, mantenga el código lo más simple posible y no se moleste en optimizarlo.