Informatica I - Esercizi sottostringhe

Esercizio di laboratorio

Argomento: manipolazione di stringhe, passaggio di parametri dalla riga di comando

Scrivere un programma che identifichi la più lunga sottostringa appartenente a due stringhe ricevute come argomenti sulla riga di comando.

Esempio: la più lunga sottostringa comune alle due stringhe PippoPluto2PaperinoMinnieAiuzzto2Zoè la stringa to2

Osservazione: questo è un caso particolare di un problema più generale, ovvero la ricerca della più lunga sottosequenza comune tra due stringhe. Si tratta di un problema molto interessante in applicazioni biologiche, in particolare nello studio del DNA. Un filamento di DNA è composto da molecole chiamate basi, e le basi possibili sono quattro: adenina (abbreviata con la lettera A), citosina (C), guanina (G) e timina (T). Dunque un filamento di DNA è rappresentabile come una stringa composta con l'alfabeto dei quattro caratteri {A,C,G,T}. Una buona misura della somiglianza tra due filamenti di DNA (ovvero della somiglianza tra due organismi) è data proprio dalla lunghezza della massima sottosequenza comune tra i due filamenti ...

Soluzione

Osservare la costruzione dei due cicli annidati (for e while), che realizzano l'algoritmo descritto.

public class MaxSubstringFinder{

public static void main(String[] args){

if (args.length != 2){

System.out.println("Uso: $java <stringa1> <stringa2>");

System.exit(1);

}

String s1 = args[0];

String s2 = args[1];

String max = ""; // conterrà la massima sottostringa comune

int start1 = 0; // conterrà l'indice di inizio di max in s1

int start2 = 0; // conterrà l'indice di inizio di max in s2

// i e' l'indice di inizio della sottostringa in s1

for (int i = 0; i < s1.length(); i++){

// j e' l'indice di inizio della sottostringa in s2

for (int j = 0; j < s2.length(); j++){

int k = 0; // k e' la lunghezza della sottostringa in esame

boolean isInSubstring = true; // è true se il char in

//esame è nella sottostringa

while (isInSubstring && i+k < s1.length() && j+k < s2.length()){

if (s1.charAt(i+k) != s2.charAt(j+k)) //la sottostringa

isInSubstring = false; //comune e' finita

else

k++;

}

if (k > max.length()) // trovata una sottostringa comune più

{ // lunga della precedente

max = s1.substring(i, i+k);

start1 = i;

start2 = j;

}

}

}

System.out.println("Massima sottostringa comune: \"" + max +"\"");

System.out.println("Indice iniziale in s1: " + start1);

System.out.println("Indice iniziale in s2: " + start2);

}

}