Spiegazione dell'algoritmo:determina se due stringhe hanno una sottostringa in comune

Istruzione del problema:date due stringhe, determina se hanno una sottostringa in comune.

Esempio:"ciao mondo" e "mondo" hanno una sottostringa in comune? Sì, entrambi hanno la sottostringa "mondo".

Approccio

Quali sono tutte le sottostringhe di string?

La stringa "parola" è lunga quattro caratteri. Contiene 10 sottostringhe di lunghezza compresa tra 1 e 4. Ecco le 10 sottostringhe:

A prima vista, potrebbe sembrare che dobbiamo scorrere tutte le sottostringhe in una stringa e controllare se quella sottostringa è contenuta nell'altra stringa. Ma possiamo fare di meglio.

Innanzitutto, l'istruzione del problema chiede solo se le due stringhe hanno almeno una sottostringa in comune. Non ci sta chiedendo di restituire le sottostringhe condivise.

In secondo luogo, nota che i singoli caratteri sono sottostringhe. Tutte le altre sottostringhe sono composte da questi singoli caratteri.

Pertanto, il problema può essere ridotto al controllo se due stringhe hanno un solo carattere in comune.

Tentativo 1:ciclo + stringa.Contiene()

Possiamo scorrere i caratteri di string1 e verificare se string2 contiene quel carattere. Possiamo uscire immediatamente dopo aver trovato una corrispondenza:

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

return falseCode language: plaintext (plaintext)

Le stringhe sono matrici di caratteri. String.Contains() esegue il ciclo su tutti i caratteri nell'array e restituisce true se il carattere esiste.

In altre parole, è un ciclo annidato. Questo è inefficiente. Nel peggiore dei casi, scorre M volte i caratteri di string2, dove M è la lunghezza di string1. È un algoritmo O(n^2).

Ad esempio, diciamo che ci viene data "parola" e "bla". Avrebbe ripetuto quattro volte tutti i caratteri in "blah":

Tentativo 2:ciclo + ricerca

Possiamo renderlo più efficiente salvando i caratteri da una stringa in una ricerca. Quindi passa sull'altra stringa e usa la ricerca per verificare la corrispondenza.

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

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

return falseCode language: plaintext (plaintext)

Fare una ricerca su un hashset è un'operazione O(1). Stiamo scorrendo ogni stringa esattamente una volta, rendendo questo un algoritmo O(n). Questo è un miglioramento dell'ordine di grandezza rispetto all'algoritmo Tentativo 1 O(n^2) in teoria. In pratica, l'utilizzo di un hashset aggiunge costi generali. Su stringhe corte, sarà effettivamente più lento dell'algoritmo O(n^2). Mostrerò un confronto delle prestazioni alla fine di questo articolo utilizzando varie dimensioni di input.

Casi di prova

Il seguente unit test parametrizzato ha 6 casi di test, che iniziano con un input non valido:

[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)

Codice

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)

Confronto delle prestazioni tra gli algoritmi O(n) e O(n^2) in pratica

Questo è un test delle prestazioni dello scenario peggiore. Nella peggiore delle ipotesi, le due stringhe non condividono un singolo carattere, il che significa che l'algoritmo deve esaminare ogni carattere in entrambe le stringhe. Sta testando stringhe con lunghezze da 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)

Ecco i risultati:

Il sovraccarico dell'utilizzo dell'hashset nell'algoritmo O(n) aggiunge circa 4 millisecondi. Questa è una costante.

Il punto di interruzione in cui O(n) inizia a diventare più veloce dell'algoritmo O(n^2) è intorno a una lunghezza di 13.000. Dopo quel punto, l'O(n^2) inizia a diventare significativamente più lento.

Questo è un buon promemoria del fatto che l'analisi Big-O non fornisce un quadro completo quando si confrontano gli algoritmi. L'analisi Big-O consiste nel confrontare i tassi di crescita degli algoritmi. In teoria, gli algoritmi O(n) dovrebbero sempre crescere più lentamente degli algoritmi O(n^2). In pratica, potrebbe esserci una grande costante che l'analisi Big-O ignora e potrebbe richiedere un grande input affinché l'algoritmo teoricamente più veloce sia effettivamente più veloce.

La chiave è conoscere la dimensione potenziale dell'input con cui hai a che fare. Se sai che hai a che fare con un input ridotto, mantieni il codice il più semplice possibile e non preoccuparti dell'ottimizzazione.