Если вход является "abba", то возможные палиндромы - это a, b, b, a, bb, abba.
Я понимаю, что определение того, является ли строка палиндром, легко. Это было бы так:
public static boolean isPalindrome(String str) {
int len = str.length();
for(int i=0; i<len/2; i++) {
if(str.charAt(i)!=str.charAt(len-i-1) {
return false;
}
return true;
}
Но какой эффективный способ найти подстроки палиндрома?
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 вперед. Поэтому общее количество повторяющихся элементов остается неизменным.
Возможно, вы могли бы выполнять итерацию по потенциальному среднему персонажу (палиндромы нечетной длины) и средние точки между символами (даже палиндромы длины) и продлевать их до тех пор, пока вы не сможете продолжить (следующие левые и правые символы не совпадают).
Это сэкономит много вычислений, если в строке не будет много палидромов. В таком случае стоимость будет равна 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++;
}
}
Итак, каждая отдельная буква уже является палиндром - так что у вас уже есть N + 1 палиндромы, где N - количество различных букв (плюс пустая строка). Вы можете сделать это за один проход - O (N).
Теперь, для нетривиальных палиндромов, вы можете проверить каждую точку своей строки как центр потенциального палиндрома - расти в обоих направлениях - что-то, что предложил Валентин Руано.
Это решение будет принимать O (N ^ 2), так как каждый тест равен O (N), а число возможных "центров" также равно O (N) - center является либо буквой, либо пробелом между двумя буквами, как и в Валентине решение.
Обратите внимание: есть также решение O (N) вашей проблемы, основанное на manacher's algoritm (статья описывает "самый длинный палиндром" , но алгоритм может использоваться для подсчета всех из них)
Я только придумал свою собственную логику, которая помогает решить эту проблему. Счастливое кодирование..: -)
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
Я предлагаю строить из базового футляра и расширяться, пока у вас не будет всех палиндомов.
Существует два типа палиндромов: четные и нечетные. Я не понял, как обращаться с обоими одинаковыми способами, поэтому я разобью его.
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 для вашей среды исполнения, но это должно быть намного эффективнее, чем попытка каждой подстроки. Худший случай - это строка всей буквы, которая может быть хуже, чем план "найти каждую подстроку", но с большинством входов он вырезает большинство подстрок, потому что вы можете перестать смотреть на него, как только вы осознаете, что это не центр палиндром.
// 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();
}
Я попробовал следующий код и его работоспособность для случаев Также он обрабатывает отдельные символы.
Несколько из переданных случаев:
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);
}
}
Надеюсь, что это будет хорошо
Код должен найти все различные подстроки, которые являются палиндромом. Вот код, который я пробовал. Он работает нормально.
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 миллисекунды