Znajdowanie wszystkich wspólnych podciągów dla dwóch ciągów znaków

Question

Natknąłem się na stwierdzenie problemu, aby znaleźć wszystkie wspólne pod-łańcuchy między podanymi dwoma pod-ciągami w taki sposób, że w każdym przypadku musisz drukować najdłuższy podciąg. Problem jest następujący:

Napisz program, aby znaleźć wspólne podciągi między dwoma podanymi ciągami. Nie należy jednak zawierać podciągów zawartych w dłuższych wspólnych podciągach.

Na przykład, biorąc pod uwagę ciągach eatsleepnightxyz i eatsleepabcxyz rezultaty powinny być:

• eatsleep (powodu eatsleepnightxyzeatsleepabcxyz)
• xyz (powodu eatsleepnightxyzeatsleepabcxyz)
• a (ze względu na eatsleepnightxyzeatsleepabcxyz)
• t (ze względu na eatsleepnightxyzeatsleepabcxyz)

Jednakże, wynikiem powinno nie obejmują e z eatsleepnightxyzeatsleepabcxyz, ponieważ oba e y jest zawarty w eatsleep wymienionych powyżej. Nie należy również włączać ea, eat, ats itd., Ponieważ są one również objęte usługą eatsleep.

W tym, że nie mają do wykorzystania Smyczkowych metod użytkowych, takich jak: zawiera indexOf, StringTokenizer, Split i wymienić.

Mój algorytm wygląda następująco: Zaczynam od brutalnej siły i przejdę do bardziej zoptymalizowanego rozwiązania, kiedy poprawię moje podstawowe zrozumienie.

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. 

Próba określenia złożoności mojego podejścia.

Niech oba podane ciągi być N1 i N2-String-String

1. Liczba podciągi S1 jest wyraźnie N1 (N1 + 1)/2.
2. Ale musimy znaleźć średnią długość podciągu S1.
3. Załóżmy, że to m. Znajdziemy m osobno.
4. Złożoność czasowa w celu sprawdzenia, czy ciąg m-string jest podciągiem ciągu n-stringowego , to O (n * m).
5. Teraz sprawdzamy, czy każdy ciąg m-string jest podciągiem S2, , który jest ciągiem n2.
6. to, jak już wcześniej wspomniano, jest O (n m) algorytmu.
7. Czas wymagany przez ogólny algorytm następnie jest
8. Tn = (Ilość podciągi w S1) * (średnia podciąg lengthtime dla procedury porównania znaków)
9. Poprzez wykonywanie niektórych obliczeń, doszedłem do wniosku, że czas złożoność jest O (n m)
10. Teraz naszym zadaniem jest znaleźć m pod względem n1.

Próba znalezienia m pod względem n1.

T _n = (n) (1) + (n-1), (2) + (n-2), (3) + ..... + (2) (N-1) + (1) (n)
gdzie T _n to suma długości wszystkich podłańcuchów.

Średnia będzie stanowić podział tej sumy przez całkowitą liczbę wyprodukowanych substratów.

to tylko jest sumowanie i podział Problem, którego rozwiązanie jest następujące O (n)

Dlatego ...

czas mojego działaniem algorytmu O (n^5).

Mając to na uwadze, napisałem poniższy kod:

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; 
} 
} 

wytłumaczenie mojego kodu:

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. 

Emisji: Biorąc pod uwagę nakłady

S1 = “neerajisgreat”; 
    S2 = “neerajisnotgreat” 
    S3 = “rajeatneerajisnotgreat” 

W przypadku S1 i S2, wyjście powinno być: neerajis i great , ale w ca se S1 i S3, wyjście powinno być: neerajis, raj, great, eat, ale nadal otrzymuję neerajis i great jako wynik. Muszę to zrozumieć.

Jak zaprojektować mój kod?

Answer 1

Lepiej wypadłbyś z odpowiednim algorytmem dla zadania, niż z podejściem brute-force. Wikipedia opisuje dwa popularne rozwiązania dla longest common substring problem: suffix-tree i dynamic-programming.

Rozwiązanie do programowania dynamicznego zajmuje O (n m) czasu i O (n m) miejsca.Jest to dość dużo proste tłumaczenie Java z Pseudokod Wikipedia dla najdłuższego wspólnego podciągu:

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; 
} 

Teraz chcesz wszystkich wspólnych podciągów, nie tylko najdłużej. Możesz ulepszyć ten algorytm, aby uwzględnić krótsze wyniki. Przeanalizujmy tabelę przykładowych wejść eatsleepnightxyz i 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 

• eatsleep wynik jest oczywisty: to jest 12345678 przekątnej passa w lewym górnym rogu.
• Wynik xyz to 123 po przekątnej u dołu po prawej stronie.
• Wynik a jest oznaczony przez 1 u góry (drugi rząd, dziewiąta kolumna).
• Wynik t jest oznaczony przez 1 w pobliżu lewego dolnego rogu.

Co z innymi 1 S w lewo, w górę, a następnie do 6 i 7? Te nie liczą się, ponieważ pojawiają się w prostokącie utworzonym przez przekątną 12345678 - innymi słowy, są już pokryte przez eatsleep.

Polecam robić jedno przejście, nie robiąc nic poza budowaniem stołu. Następnie wykonaj drugie przejście, powtarzając od tyłu od dołu w prawo, aby zebrać zestaw wyników.

Answer 2

Zazwyczaj ten typ dopasowywania podła jest wykonywany przy pomocy oddzielnej struktury danych o nazwie Trie (wymawiana próba). Konkretnym wariantem najlepiej odpowiadającym temu problemowi jest suffix tree. Pierwszym krokiem powinno być pobranie danych wejściowych i utworzenie drzewa sufiksów. Następnie należy użyć drzewa sufiksów w celu określenia najdłuższego wspólnego podciągu, co jest dobrym ćwiczeniem.