Znajdź wszystkie podciągi będące palindromami

Być może mógłbyś iterować pomiędzy potencjalnymi średnimi znakami (palindromy o nieparzystej długości) i średnimi punktami między znakami (palindromy o parzystej długości) i rozszerzyć każdy z nich, aż nie będziesz mógł dostać się dalej(kolejne lewe i prawe znaki nie pasują).

To zaoszczędziłoby wiele obliczeń, gdy nie ma wielu palidromów w łańcuchu. W takim przypadku koszt byłby O (n)dla strun palidromowych.

Dla gęstych wejść palindromu byłoby O (n^2), ponieważ każda pozycja nie może być rozszerzona o więcej niż długość tablicy / 2. Oczywiście jest to jeszcze mniej na końcach tablicy.

  public Set<String> palindromes(final String input) {

     final Set<String> result = new HashSet<>();

     for (int i = 0; i < input.length(); i++) {
         // expanding even length palindromes:
         expandPalindromes(result,input,i,i+1);
         // expanding odd length palindromes:
         expandPalindromes(result,input,i,i);
     } 
     return result;
  }

  public void expandPalindromes(final Set<String> result, final String s, int i, int j) {
      while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            result.add(s.substring(i,j+1));
            i--; j++;
      }
  }

Więc, każda odrębna litera jest już palindromem - więc masz już N + 1 palindromów, gdzie N jest liczbą odrębnych liter (plus pusty ciąg). Można to zrobić w jednym biegu-O (N).

Teraz, dla nietrywialnych palindromów, możesz przetestować każdy punkt twojego ciągu, aby był centrum potencjalnego palindromu-rosnącego w obu kierunkach-coś, co zasugerował Valentin Ruano .
Rozwiązanie to zajmie O(N^2), ponieważ każdy test to O (N) i liczba możliwych "Centra" to także O ( N) - center jest literą lub spacją między dwiema literami, podobnie jak w rozwiązaniu Valentina.

Uwaga, Istnieje również O(N) rozwiązanie twojego problemu, oparte na algorytmie Manachera (artykuł opisuje "najdłuższy palindrom", ale algorytm może być użyty do zliczenia wszystkich z nich)

Właśnie wymyśliłem własną logikę, która pomaga rozwiązać ten problem. Szczęśliwego kodowania.. :-)

System.out.println("Finding all palindromes in a given string : ");
        subPal("abcacbbbca");

private static void subPal(String str) {
        String s1 = "";
        int N = str.length(), count = 0;
        Set<String> palindromeArray = new HashSet<String>();
        System.out.println("Given string : " + str);
        System.out.println("******** Ignoring single character as substring palindrome");
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                int k = i + j - 1;
                if (k >= N)
                    continue;
                s1 = str.substring(j, i + j);
                if (s1.equals(new StringBuilder(s1).reverse().toString())) {
                    palindromeArray.add(s1);
                }
            }

        }
        System.out.println(palindromeArray);
        for (String s : palindromeArray)
            System.out.println(s + " - is a palindrome string.");
        System.out.println("The no.of substring that are palindrome : "
                + palindromeArray.size());
    }

Output:-
Finding all palindromes in a given string : 
Given string : abcacbbbca
******** Ignoring single character as substring palindrome ********
[cac, acbbbca, cbbbc, bb, bcacb, bbb]
cac - is a palindrome string.
acbbbca - is a palindrome string.
cbbbc - is a palindrome string.
bb - is a palindrome string.
bcacb - is a palindrome string.
bbb - is a palindrome string.
The no.of substring that are palindrome : 6

Sugeruję rozbudowę bazy i rozbudowę, aż będziesz miał wszystkie palindomy.

1) Dodaj wszystkie pojedyncze litery

2) z tej listy masz wszystkie punkty wyjścia dla swoich palindromów. Uruchom każde z nich dla każdego indeksu w łańcuchu (lub 1- > Długość-1, ponieważ potrzebujesz co najmniej 2 długość): {]}

findAllEvenFrom(int index){
  int i=0;
  while(true) {
    //check if index-i and index+i+1 is within string bounds

    if(str.charAt(index-i) != str.charAt(index+i+1)) 
      return; // Here we found out that this index isn't a center for palindromes of >=i size, so we can give up

    outputList.add(str.substring(index-i, index+i+1));
    i++;
  }
}
//Odd looks about the same, but with a change in the bounds.
findAllOddFrom(int index){
  int i=0;
  while(true) {
    //check if index-i and index+i+1 is within string bounds

    if(str.charAt(index-i-1) != str.charAt(index+i+1)) 
      return;

    outputList.add(str.substring(index-i-1, index+i+1));
    i++;
  }
}

Nie jestem pewien, czy to pomaga Big-O w Twoim uruchomieniu, ale powinno być o wiele wydajniejsze niż próbowanie każdego fragmentu. Najgorszym przypadkiem będzie łańcuch wszystkich tych samych liter, który może być gorszy niż plan "znajdź każdy podłańcuch", ale przy większości wejść wytnie większość podłańcuchów, ponieważ możesz przestać patrzeć na jeden z nich, gdy uświadomisz sobie, że nie jest on centrum palindromu.

    // Maintain an Set of palindromes so that we get distinct elements at the end
    // Add each char to set. Also treat that char as middle point and traverse through string to check equality of left and right char


static int palindrome(String str) {

    Set<String> distinctPln = new HashSet<String>();
    for (int i=0; i<str.length();i++) {
        distinctPln.add(String.valueOf(str.charAt(i)));
        for (int j=i-1, k=i+1; j>=0 && k<str.length(); j--, k++) {
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(j)))) { 
                distinctPln.add(str.substring(j,i+1));
            }
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(i,k+1));
            }
            if ( (new Character(str.charAt(j))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(j,k+1));
            } else {
                continue;
            }
        }
    }

    Iterator<String> distinctPlnItr = distinctPln.iterator();
    while ( distinctPlnItr.hasNext()) {
        System.out.print(distinctPlnItr.next()+ ",");
    }
    return distinctPln.size();

}

Wypróbowałem następujący kod i działa dobrze dla przypadków Obsługuje również pojedyncze znaki

Kilka spraw, które przeszły:

abaaa --> [aba, aaa, b, a, aa] 
geek  --> [g, e, ee, k] 
abbaca --> [b, c, a, abba, bb, aca] 
abaaba -->[aba, b, abaaba, a, baab, aa] 
abababa -->[aba, babab, b, a, ababa, abababa, bab] 
forgeeksskeegfor --> [f, g, e, ee, s, r, eksske, geeksskeeg, 
                      o, eeksskee, ss, k, kssk]

Kod

static Set<String> set = new HashSet<String>(); 
static String DIV = "|";

public static void main(String[] args) {
    String str = "abababa";
    String ext = getExtendedString(str);

    // will check for even length palindromes
    for(int i=2; i<ext.length()-1; i+=2) {
        addPalindromes(i, 1, ext);
    }
    // will check for odd length palindromes including individual characters
    for(int i=1; i<=ext.length()-2; i+=2) {
        addPalindromes(i, 0, ext);
    }
    System.out.println(set);
}

/*
 * Generates extended string, with dividors applied
 * eg: input = abca
 * output = |a|b|c|a|
 */
static String getExtendedString(String str) {
    StringBuilder builder = new StringBuilder();
    builder.append(DIV);
    for(int i=0; i< str.length(); i++) {
        builder.append(str.charAt(i));
        builder.append(DIV);

    }
    String ext = builder.toString();
    return ext;
}

/*
 * Recursive matcher
 * If match is found for palindrome ie char[mid-offset] = char[mid+ offset]
 * Calculate further with offset+=2
 * 
 * 
 */
static void addPalindromes(int mid, int offset, String ext) {
    // boundary checks
    if(mid - offset <0 || mid + offset > ext.length()-1) {
        return;
    }
    if (ext.charAt(mid-offset) == ext.charAt(mid+offset)) {
        set.add(ext.substring(mid-offset, mid+offset+1).replace(DIV, ""));
        addPalindromes(mid, offset+2, ext);
    }
}

Hope its fine

Kod polega na znalezieniu wszystkich osobnych podłańcuchów, które są palindromami. Oto kod, którego próbowałem. Działa dobrze.

import java.util.HashSet;
import java.util.Set;

public class SubstringPalindrome {

    public static void main(String[] args) {
        String s = "abba";
        checkPalindrome(s);
}

public static int checkPalindrome(String s) {
    int L = s.length();
    int counter =0;
    long startTime = System.currentTimeMillis();
    Set<String> hs = new HashSet<String>();
    // add elements to the hash set
    System.out.println("Possible substrings: ");
    for (int i = 0; i < L; ++i) {
      for (int j = 0; j < (L - i); ++j) {
          String subs = s.substring(j, i + j + 1);
            counter++;
            System.out.println(subs);
            if(isPalindrome(subs))
                hs.add(subs);
      }
    }
    System.out.println("Total possible substrings are "+counter);
    System.out.println("Total palindromic substrings are "+hs.size());
    System.out.println("Possible palindromic substrings: "+hs.toString());
    long endTime = System.currentTimeMillis();
    System.out.println("It took " + (endTime - startTime) + " milliseconds");
    return hs.size();
}
public static boolean isPalindrome(String s) {
    if(s.length() == 0 || s.length() ==1)
        return true;
    if(s.charAt(0) ==  s.charAt(s.length()-1))
        return isPalindrome(s.substring(1, s.length()-1));
    return false;
}

}

Wyjście:

Możliwe podciągi: a b b a ab bb ba abb bba abba

Suma możliwych podciągów wynosi 10

Suma podpór palindromicznych wynosi 4

Możliwe podciągi palindromiczne: [bb, a, B, abba]

Zajęło 1 milisekundę