Найти все подстроки, которые являются палиндромами

Ответ 1

Это можно сделать в O(n), используя алгоритм Manacher.

Основная идея - сочетание динамического программирования и (как уже говорили другие), вычисление максимальной длины палиндрома с центром в данной букве.

То, что мы действительно хотим рассчитать, - это радиус самого длинного палиндрома, а не длина. Радиус просто length/2 или (length - 1)/2 (для палиндромов нечетной длины).

После вычисления радиуса палиндрома pr в заданном положении i мы используем уже рассчитанные радиусы для поиска палиндромов в диапазоне [ i - pr ; i ]. Это позволяет нам (потому что палиндромы, ну, палиндромы) пропустить дальнейшее вычисление radiuses для диапазона [ i ; i + pr ].

При поиске в диапазоне [ i - pr ; i ] для каждой позиции i - k существует четыре основных случая (где k находится в 1,2,... pr):

• нет палиндрома (radius = 0) на i - k
  (это означает radius = 0 в i + k тоже)
• внутренний палиндром, что означает, что он соответствует диапазону (это означает, что radius at i + k совпадает с i - k)
• внешний палиндром, что означает, что он не соответствует диапазону (это означает, что radius at i + k сокращается, чтобы соответствовать диапазону, т. к. i + k + radius > i + pr мы уменьшаем radius до pr - k)
• липкий палиндром, что означает i + k + radius = i + pr
  (в этом случае нам нужно искать потенциально больший радиус при i + k)

Полное подробное объяснение будет довольно продолжительным. Как насчет некоторых образцов кода?:)

Я нашел С++ реализацию этого алгоритма польским преподавателем, господином Ежи Валашеком.
Я перевел комментарии на английский язык, добавил некоторые другие комментарии и упростил его, чтобы легче было поймать основную часть.
Посмотрите здесь.

Примечание: в случае проблем, понимающих, почему это O(n), попробуйте посмотреть так:
после нахождения радиуса (назовем его r) в некоторой позиции, нам нужно выполнить итерацию по элементам r, но в результате мы можем пропустить вычисление для элементов r вперед. Поэтому общее количество повторяющихся элементов остается неизменным.

Ответ 2

Возможно, вы могли бы выполнять итерацию по потенциальному среднему персонажу (палиндромы нечетной длины) и средние точки между символами (даже палиндромы длины) и продлевать их до тех пор, пока вы не сможете продолжить (следующие левые и правые символы не совпадают).

Это сэкономит много вычислений, если в строке не будет много палидромов. В таком случае стоимость будет равна O (n) для разреженных палидровых строк.

Для палиндромных плотных входов это будет O (n ^ 2), так как каждая позиция не может быть увеличена больше, чем длина массива /2. Очевидно, это еще меньше по отношению к концам массива.

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

Ответ 3

Итак, каждая отдельная буква уже является палиндром - так что у вас уже есть N + 1 палиндромы, где N - количество различных букв (плюс пустая строка). Вы можете сделать это за один проход - O (N).

Теперь, для нетривиальных палиндромов, вы можете проверить каждую точку своей строки как центр потенциального палиндрома - расти в обоих направлениях - что-то, что предложил Валентин Руано.
Это решение будет принимать O (N ^ 2), так как каждый тест равен O (N), а число возможных "центров" также равно O (N) - center является либо буквой, либо пробелом между двумя буквами, как и в Валентине решение.

Обратите внимание: есть также решение O (N) вашей проблемы, основанное на manacher's algoritm (статья описывает "самый длинный палиндром" , но алгоритм может использоваться для подсчета всех из них)

Ответ 4

Я только придумал свою собственную логику, которая помогает решить эту проблему. Счастливое кодирование..: -)

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

Ответ 5

Я предлагаю строить из базового футляра и расширяться, пока у вас не будет всех палиндомов.

Существует два типа палиндромов: четные и нечетные. Я не понял, как обращаться с обоими одинаковыми способами, поэтому я разобью его.

1) Добавить все отдельные буквы

2) С этим списком у вас есть все начальные точки для ваших палиндромов. Запустите каждый из них для каждого индекса в строке (или 1 → длина-1, потому что вам нужно как минимум 2 длины):

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

Я не уверен, что это помогает Big-O для вашей среды исполнения, но это должно быть намного эффективнее, чем попытка каждой подстроки. Худший случай - это строка всей буквы, которая может быть хуже, чем план "найти каждую подстроку", но с большинством входов он вырезает большинство подстрок, потому что вы можете перестать смотреть на него, как только вы осознаете, что это не центр палиндром.

Ответ 6

    // 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();

}

Ответ 7

Я попробовал следующий код и его работоспособность для случаев Также он обрабатывает отдельные символы.

Несколько из переданных случаев:

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]

Код

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

Надеюсь, что это будет хорошо

Ответ 8

Код должен найти все различные подстроки, которые являются палиндромом. Вот код, который я пробовал. Он работает нормально.

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

}

ВЫВОД:

Возможные подстроки: б б аб бб ба уток BBA авва

Всего возможных подстрок 10

Всего палиндромных подстрок 4

Возможные палиндромные подстроки: [bb, a, b, abba]

Прошло 1 миллисекунды