Mi sono imbattuto in una dichiarazione di problema per trovare il tutte le stringhe secondarie comuni tra le due stringhe specificate in modo tale che in ogni caso è necessario stampare il più lungo sub-stringa. La dichiarazione del problema è la seguente:Trovare tutte le sottostringhe comuni di due stringhe date
Scrivere un programma per trovare le sottostringhe comuni tra le due stringhe fornite. Tuttavia, non includere sottostringhe contenute in sottostringhe più comuni.
Ad esempio, date le stringhe di input
eatsleepnightxyz
eeatsleepabcxyz
, i risultati dovrebbero essere:
eatsleep
(dovutoeatsleepnightxyz
eatsleepabcxyz
)xyz
(dovutoeatsleepnightxyz
eatsleepabcxyz
)a
(causaeatsleepnightxyz
eatsleepabcxyz
)t
(dovutoeatsleepnightxyz
eatsleepabcxyz
)Tuttavia, il set di risultati dovrebbe non includere
e
daeatsleepnightxyz
eatsleepabcxyz
, perché entrambie
s sono già contenuti neleatsleep
cui sopra. Né dovresti includereea
,eat
,ats
, ecc., Poiché anche queste sono coperte daeatsleep
.In questo, non è necessario utilizzare i metodi di utilità String come: contiene, indexOf, StringTokenizer, split e replace.
Il mio Algorithm è il seguente: Sto iniziando con la forza bruta e passerò a una soluzione più ottimizzata quando migliorerò la mia comprensione di base.
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.
Tentativo di calcolare la complessità temporale del mio approccio.
Let due stringhe date siano n1-String e n2-String
- Il numero di sottostringhe S1 è chiaramente n1 (n1 + 1)/2.
- Ma dobbiamo trovare la lunghezza media di una sottostringa di S1.
- Diciamo che è m. Troveremo m separatamente.
- Complessità del tempo per verificare se una m-stringa è una sottostringa di una stringa n. è O (n * m).
- Ora, stiamo verificando che ogni m-String è una sottostringa di S2, che è una stringa n2.
- Questo, come abbiamo visto sopra, è un algoritmo O (n m).
- Il tempo richiesto dall'algoritmo generale poi è
- Tn = (Numero di sottostringhe in S1) * (lengthtime media sottostringa procedura di confronto carattere)
- Eseguendo alcuni calcoli, sono giunto alla conclusione che il tempo la complessità è O (n m)
- Ora, il nostro lavoro è trovare m in termini di n1.
Tentativo di trovare m in termini di n1.
T n = (n) (1) + (n-1) (2) + (n-2) (3) + ..... + (2) (n-1) + (1) (n)
dove T n è la somma delle lunghezze di tutte le sottostringhe.
La media sarà la divisione di questa somma per il numero totale di sottostringhe prodotte.
Questo, semplicemente è un problema somma e divisione la cui soluzione è la seguente O (n)
Quindi ...
momento del mio algoritmo di esecuzione è O (n^5).
Con questo in mente ho scritto il seguente codice:
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;
}
}
Spiegazione per il mio codice:
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: Date le ingressi
S1 = “neerajisgreat”;
S2 = “neerajisnotgreat”
S3 = “rajeatneerajisnotgreat”
In caso di S1 e S2, l'output dovrebbe essere: neerajis
e great
ma in ca Se di S1 e S3, l'output avrebbe dovuto essere: neerajis
, raj
, great
, eat
ma sto ricevendo neerajis
e great
come output. Devo capirlo.
Come devo progettare il mio codice?
Se hai risolto questo problema, potresti condividere la tua soluzione? – delca85