2016-01-15 23 views
15

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 e eatsleepabcxyz, i risultati dovrebbero essere:

  • eatsleep (dovuto eatsleepnightxyzeatsleepabcxyz)
  • xyz (dovuto eatsleepnightxyzeatsleepabcxyz)
  • a (causa eatsleepnightxyzeatsleepabcxyz)
  • t (dovuto eatsleepnightxyzeatsleepabcxyz)

Tuttavia, il set di risultati dovrebbe non includere e da eatsleepnightxyzeatsleepabcxyz, perché entrambi e s sono già contenuti nel eatsleep cui sopra. Né dovresti includere ea, eat, ats, ecc., Poiché anche queste sono coperte da eatsleep.

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

  1. Il numero di sottostringhe S1 è chiaramente n1 (n1 + 1)/2.
  2. Ma dobbiamo trovare la lunghezza media di una sottostringa di S1.
  3. Diciamo che è m. Troveremo m separatamente.
  4. Complessità del tempo per verificare se una m-stringa è una sottostringa di una stringa n. è O (n * m).
  5. Ora, stiamo verificando che ogni m-String è una sottostringa di S2, che è una stringa n2.
  6. Questo, come abbiamo visto sopra, è un algoritmo O (n m).
  7. Il tempo richiesto dall'algoritmo generale poi è
  8. Tn = (Numero di sottostringhe in S1) * (lengthtime media sottostringa procedura di confronto carattere)
  9. Eseguendo alcuni calcoli, sono giunto alla conclusione che il tempo la complessità è O (n m)
  10. 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?

+0

Se hai risolto questo problema, potresti condividere la tua soluzione? – delca85

risposta

8

Sarebbe meglio con un algoritmo adeguato per l'attività piuttosto che con un approccio a forza bruta. Wikipedia descrive due soluzioni comuni a longest common substring problem: e .

La soluzione programmazione dinamica richiederà O (n m) tempo e O (n m) spazio.Questo è più o meno una semplice traduzione Java del pseudocodice Wikipedia per la più lunga sottostringa comune:

public static Set<String> longestCommonSubstrings(String s, String t) { 
    int[][] table = new int[s.length()][t.length()]; 
    int longest = 0; 
    Set<String> result = new HashSet<>(); 

    for (int i = 0; i < s.length(); i++) { 
     for (int j = 0; j < t.length(); j++) { 
      if (s.charAt(i) != t.charAt(j)) { 
       continue; 
      } 

      table[i][j] = (i == 0 || j == 0) ? 1 
              : 1 + table[i - 1][j - 1]; 
      if (table[i][j] > longest) { 
       longest = table[i][j]; 
       result.clear(); 
      } 
      if (table[i][j] == longest) { 
       result.add(s.substring(i - longest + 1, i + 1)); 
      } 
     } 
    } 
    return result; 
} 

Ora, si desidera che tutti i sottostringhe comuni, non solo il più lungo. È possibile migliorare questo algoritmo per includere risultati più brevi. Esaminiamo la tabella Per l'esempio, ingressi eatsleepnightxyz e eatsleepabcxyz:

e a t s l e e p a b c x y z 
e 1 0 0 0 0 1 1 0 0 0 0 0 0 0 
a 0 2 0 0 0 0 0 0 1 0 0 0 0 0 
t 0 0 3 0 0 0 0 0 0 0 0 0 0 0 
s 0 0 0 4 0 0 0 0 0 0 0 0 0 0 
l 0 0 0 0 5 0 0 0 0 0 0 0 0 0 
e 1 0 0 0 0 6 1 0 0 0 0 0 0 0 
e 1 0 0 0 0 1 7 0 0 0 0 0 0 0 
p 0 0 0 0 0 0 0 8 0 0 0 0 0 0 
n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
i 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
g 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
t 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
x 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
y 0 0 0 0 0 0 0 0 0 0 0 0 2 0 
z 0 0 0 0 0 0 0 0 0 0 0 0 0 3 
  • Il eatsleep risultato è evidente: questa è la striscia diagonale 12345678 in alto a sinistra.
  • Il risultato xyz corrisponde alla diagonale 123 in basso a destra.
  • Il risultato a è indicato dallo 1 in alto (seconda riga, nona colonna).
  • Il risultato t è indicato dallo 1 in basso a sinistra.

E gli altri 1 s a sinistra, la parte superiore, e vicino al 6 e 7? Quelli non contano perché appaiono all'interno del rettangolo formato dalla diagonale 12345678 - in altre parole, sono già coperti da eatsleep.

Suggerisco di fare un passaggio senza fare altro che costruire il tavolo. Quindi, effettua una seconda passata, iterando all'indietro dal basso a destra, per raccogliere il set di risultati.

+0

Lasciaci [continuare questa discussione in chat] (http://chat.stackoverflow.com/rooms/100826/discussion-between-neeraj-dorle-and-200-success). – neerajdorle

5

In genere questo tipo di corrispondenza della sottostringa viene eseguita con l'assistenza di una struttura dati separata denominata Trie (pronunciata try). La variante specifica che si adatta meglio a questo problema è una suffix tree. Il tuo primo passo dovrebbe essere quello di prendere i tuoi input e costruire un albero di suffisso. Quindi dovrai usare l'albero del suffisso per determinare la sottostringa comune più lunga, che è un buon esercizio.

Problemi correlati