Най-дълъг палиндром подниз в низ в Java

Най-дълъг палиндром подниз в низ в Java

Въведение

Палиндром е низ, който се чете еднакво както отляво надясно, така и отдясно наляво, като популярни примери са „anna“ и „racecar“. Идентифицирането на най-дългия палиндром подниз в даден низ е често срещан проблем в обработката на текстове и има множество приложения в обработката на данни и алгоритмите. В Java можем да използваме различни подходи за решаване на този проблем, включително брутална сила, динамично програмиране и алгоритми на Манакер.

Алгоритъм с брутална сила

Алгоритъмът с брутална сила е най-простият подход за намиране на най-дългия палиндром подниз. Той проверява всички възможни поднизове в дадения низ, сравнява всеки подниз с неговия обратен низ и запазва най-дългия намерен палиндром.

java
public static String longestPalindrome(String str) {
int n = str.length();
String longest = "";
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
String sub = str.substring(i, j);
if (sub.equals(new StringBuilder(sub).reverse().toString()) && sub.length() > longest.length()) {
longest = sub;
}
}
}
return longest;
}


Алгоритъм с динамично програмиране

Алгоритъмът с динамично програмиране използва таблица за съхраняване на информация за предишни изчисления. Той създава двумерна таблица dp, където dp[i][j] е true, ако поднизът от индекс i до индекс j е палиндром. Алгоритъмът попълва таблицата, като работи от по-малките поднизове към по-големите и запазва най-дългия намерен палиндром.

java
public static String longestPalindrome(String str) {
int n = str.length();
boolean[][] dp = new boolean[n][n];
String longest = "";
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (str.charAt(i) == str.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (j - i + 1 > longest.length()) {
longest = str.substring(i, j + 1);
}
}
}
}
return longest;
}


Алгоритъм на Манакер

Алгоритъмът на Манакер е ефективен линейновременен алгоритъм за намиране на най-дългия палиндром подниз. Той работи чрез разширяване около всеки индекс и запазване на границите на разширенията. В Java можем да имплементираме алгоритъма на Манакер, използвайки клас, който разширява разширенията стъпка по стъпка.

java
public class Manacher {

public String longestPalindrome(String str) {
int n = str.length();
int[] p = new int[n];
int center = 0, right = 0;
int maxLen = 0;
String longest = "";
for (int i = 1; i < n - 1; i++) {
int mirror = 2 * center - i;
p[i] = right > i ? Math.min(right - i, p[mirror]) : 0;
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && str.charAt(i - p[i] - 1) == str.charAt(i + p[i] + 1)) {
p[i]++;
}
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
if (p[i] > maxLen) {
maxLen = p[i];
longest = str.substring(i - maxLen, i + maxLen + 1);
}
}
return longest;
}
}


Заключение

Идентифицирането на най-дългия палиндром подниз е важен проблем в обработката на текстове с множество приложения. Представените в тази статия алгоритми предоставят различни подходи за решаване на този проблем, като всеки алгоритъм има своите предимства и недостатъци. Изборът на най-подходящия алгоритъм зависи от конкретните изисквания и характеристики на данните.

Често задавани въпроси

1. Каква е сложността на алгоритъма с брутална сила?
Алгоритъмът с брутална сила има квадратична сложност O(n^2), където n е дължината на низа.

2. Каква е сложността на алгоритъма с динамично програмиране?
Алгоритъмът с динамично програмиране има кубична сложност O(n^3), където n е дължината на низа.

3. Кога да използвам алгоритъма на Манакер?
Алгоритъмът на Манакер е подходящ за големи низове, тъй като има линейновременна сложност O(n), където n е дължината на низа.

4. Възможно ли е да съществуват множество най-дълги палиндромни поднизове?
Да, възможно е да съществуват множество най-дълги палиндромни поднизове в един низ.

5. Как да намеря всички най-дълги палиндромни поднизове в един низ?
Можем да проследим диагоналите в таблицата dp в алгоритъма с динамично програмиране, за да идентифицираме всички най-дълги палиндромни поднизове.

6. Защо таблицата dp в алгоритъма с динамично програмиране има размер [n][n]?
Всеки подниз се представя от клетка в таблицата dp, където редът е началният индекс на подниза, а колоната е краен индекс.

7. Кой алгоритъм е най-ефективен за намиране на най-дългия палиндром подниз?
Алгоритъмът на Манакер обикновено се счита за най-ефективния за големи низове поради неговата линейновременна сложност.

8. Има ли имплементации на these алгоритми в популярни Java библиотеки?
Да, популярни Java библиотеки като Apache Commons Lang и Guava предоставят имплементации на алгоритми за намиране на най-дългия палиндром подниз.