Podciągi w Javie

Najpopularniejszymi działaniami wykonywanymi na String-ach w Javie są konkatenacja, pobieranie znaku z indeksu oraz pobieranie podciągu. W tym artykule opowiemy o metodzie substring (ang. podciąg) w Javie.

Czym jest podciąg w Javie?

Ogólnie podciąg jest ciągłą sekwencją znaków wewnątrz Stringa. Może to być również cały ciąg lub jego część. Ten język ma metodę substring(), a właściwie dwie takie metody, dzięki przeciążaniu metod w Javie. Można je użyć do uzyskania podciągu. Pierwsza metoda substring w Javie to String substring(firstIndex), a druga to String substring (firstIndex, lastIndex).

Jak używać metody substring w Javie

Odpowiedź jest prosta: wystarczy użyć podciągu. Metoda Java substring() zwraca część ciągu. Możesz to zrobić na dwa sposoby: Bardzo popularne zadania, które pomagają zrozumieć...

• Jak uzyskać podciąg w Javie
• Jak znaleźć wszystkie podciągi danego ciągu?
• Jak znaleźć najdłuższy wspólny podciąg

Jak uzyskać podciąg w Javie (konkretny)

Ten pierwszy przykład dot. substring w Javie jest dość prosty. Masz String i musisz znaleźć w nim podciąg „CodeGym”. Wiesz już, jak uzyskać podciąg w Javie. Oto rozwiązanie tego konkretnego problemu:

import java.io.IOException;

public class Main {

   public static void main(String[] args) throws IOException {

       String s1 = "the best Java Core course is CourseCodeGym.  End of story";
       String myTarget = "CodeGym";
       int index1 = s1.indexOf(myTarget);
      
       int index2 = index1 + myTarget.length();
       System.out.println(s1.substring(index1, index2));

   }
}

Wyświetlone zostanie:

Jak znaleźć wszystkie podciągi danego ciągu

Oto najprostszy sposób na znalezienie wszystkich podciągów danego Stringu.

import java.io.IOException;
public class Main {
   public static void main(String[] args) throws IOException {
       String myTarget = "CodeGym";
       for (int i = 0; i < myTarget.length(); i++) {
           for (int j = i + 1; j <= myTarget.length(); j++) {
               System.out.println(myTarget.substring(i, j));
           }
       }    
   }
}

Wyświetlone zostanie:

Jak znaleźć najdłuższy wspólny podciąg

Problem najdłuższego wspólnego podciągu jest jednym z najpopularniejszych zadań w informatyce. Z dość dużym prawdopodobieństwem możesz się z nim spotkać na rozmowie kwalifikacyjnej dotyczącej posady Junior Developer. W każdym razie spróbuj go rozwiązać, bo jest to bardzo przydatne ćwiczenie dla początkującego programisty. Problem najdłuższego wspólnego podciągu polega na znalezieniu najdłuższego ciągu (lub kilku takich ciągów), który jest podciągiem (lub są podciągami) dwóch lub więcej stringów. Jako przykład weźmy dwa ciągi

String first = "CodeGym" 
String second = "SomeGym"

Wydrukiem powinno być: Tak więc musisz wprowadzić ciągi „first” i „second”. Wydrukuj najdłuższy wspólny podciąg. Jeśli dwa lub więcej podciągów ma tę samą wartość dla najdłuższego wspólnego podciągu, wydrukuj dowolny z nich. Zalecamy samodzielną próbę rozwiązania tego problemu przed zapoznaniem się z poniższym kodem.

public class SubStringTest {

   //  in this method we are looking for the Longest common substring of
   // first String with length = m  and the second String with length = n
   public static String longestCS(String first, String second, int m, int n) {
       // the maximal length
       int maxLength = 0;
       // the last index of the longest common substring
       int endIndex = m;

       // array stores the length of substring
       int[][] keeper = new int[m + 1][n + 1];

       for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
               // check if current characters of first and second strings match
               if (first.charAt(i - 1) == second.charAt(j - 1)) {
                   keeper[i][j] = keeper[i - 1][j - 1] + 1;
                  
                   if (keeper[i][j] > maxLength) {
                       maxLength = keeper[i][j];
                       endIndex = i;
                   }
               }
           }
       }
       return first.substring(endIndex - maxLength, endIndex);
   }


   public static void main(String[] args) {
       String first = "CodeGym";
       String second = "SomeGym";
       int m = first.length(), n = second.length();
       System.out.println("The longest common substring = " + longestCS(first, second, m, n));
   }
}

Wyświetlone zostanie:

Jak działa podciąg w Javie?

W JDK 7 i nowszych wersjach substring() nie liczy już liczby znaków w tworzonej tablicy znaków, jak to miało miejsce w wersjach wcześniejszych niż JDK 6 włącznie, lecz po prostu tworzy nową tablicę w pamięci (stercie, ang. heap) i odwołuje się do niej. Oto przykład:

String x = "CodeGymIsTheBest";
String y = x.substring (2,6);
String z = x.substring (0,3);

Tak więc w JDK 7 i nowszych obiekty y i z utworzone w wyniku zastosowania metody substring() do obiektu x będą odwoływać się do dwóch nowo utworzonych tablic (na stercie) - {d, e, G, y} dla y i {C, o} dla z. W wersji JDK 7+ metody substring te dwa nowe wiersze (czyli dwie nowe tablice znaków) będą przechowywane w pamięci wraz z oryginalnym ciągiem myLongString ({C, o, d, e, G, y, m, i, s, t, h, e, b, e, s, t} w postaci tablicy).

Wersja JDK 6 podciągu

Nawet dzisiaj w niektórych dużych projektach można spotkać się ze starszą bazą kodu z czasów JDK 6. W JDK 6 metoda substring() działa w inny sposób. Jak zapewne wiesz, String jest klasą niezmienną i w celu uzyskania podciągu Java wykorzystała tę niezmienność już w JDK 6. Obiekt typu String w środku jest po prostu tablicą znaków, a raczej zawiera tablicę znaków. W czasach JDK 6 przechowywano tam jeszcze dwie zmienne: numer pierwszego znaku w tablicy znaków oraz ich liczbę. Tak więc w JDK 6 String miał trzy pola char value [] (tablica znaków), int offset (indeks pierwszego znaku w tablicy) i int count (liczba znaków w tablicy). Gdy w JDK 6 tworzony jest podciąg, tablica znaków nie jest kopiowana do nowego obiektu String. Zamiast tego oba obiekty przechowują odniesienie do tej samej tablicy znaków. Jednak drugi obiekt przechowuje jeszcze dwie zmienne: pierwszą — symbol podciągu oraz drugą — informację o tym, ile symboli znajduje się w podciągu. Metoda z JDK 6 została zastąpiona z powodu problemów z wyciekiem pamięci. Co to oznacza? Załóżmy, że mamy ciąg x i tworzymy kilka podciągów za pomocą metody substring.

String x = "CodeGymIsTheBest";
String y = x.substring (2,6);
String z = x.substring (0,3);

Mamy teraz obiekt x przechowywany w specjalnym obszarze pamięci zwanym stertą oraz dwa obiekty y i z odnoszące się do tego samego obiektu x. Tylko x odnosi się do elementów od drugiego do szóstego, natomiast z do x od zera do trzeciego. Co zrobić, jeśli oryginalny obiekt x został już użyty i nie ma do niego żadnych odniesień? W programie wszystkie inne obiekty działają tylko z y i z. W takim przypadku śmierciarka (ang. garbage collector) może zniszczyć obiekt x, natomiast tablica pamięci pozostaje i jest używana przez y oraz z. Dochodzi do wycieku pamięci. Tak więc w wersjach JDK 7 i nowszych metoda jest dość kosztowna pod względem wykorzystania pamięci. Pozwala to jednak zapobiec jej wyciekom. Ponadto nowa metoda działa szybciej, ponieważ nie musi obliczać liczby znaków.