Найдовший підрядок паліндрому в рядку в Java

Вступ

У світі інформаційних технологій, зокрема в біоінформатиці та обробці текстових даних, часто виникає необхідність виявити найбільший паліндромний фрагмент у заданому рядку. Паліндромом називають послідовність символів, яка читається ідентично з обох боків, як наприклад “мадам” чи “радар”.

Існує декілька методів розв’язання цієї задачі, кожен з яких має свої сильні та слабкі сторони, що залежать від конкретних вимог. У цій статті ми розглянемо один з найефективніших підходів – алгоритм Манакера, і продемонструємо його застосування за допомогою мови програмування Java.

Алгоритм Манакера: детальний огляд

Алгоритм Манакера – це лінійний алгоритм, що дозволяє знайти найдовший паліндромний підрядок за час, пропорційний довжині рядка O(n). Цей алгоритм використовує ряд технік для прискорення пошуку:

  • Перетворення рядка: Початковий рядок модифікується шляхом вставки спеціальних символів, таких як “$” на початку та “#” між кожною парою символів. Це дозволяє обробляти паліндроми як парної, так і непарної довжини однаково.
  • Застосування таблиці радіусів: Алгоритм зберігає інформацію про радіуси паліндромів з центром в кожній позиції рядка у спеціальній таблиці. Ця таблиця використовується для швидкого розширення паліндромів та зменшення зайвих обчислень.

Реалізація алгоритму Манакера на Java

Нижче представлено код алгоритму Манакера, написаний на Java:

public class PalindromeSubstring {

    public static String findLongestPalindrome(String str) {
        // Модифікація рядка
        StringBuilder sb = new StringBuilder("$#");
        for (char c : str.toCharArray()) {
            sb.append(c).append('#');
        }
        sb.append('$');
        String modifiedString = sb.toString();

        // Ініціалізація таблиці радіусів
        int[] radius = new int[modifiedString.length()];

        // Змінні для відстеження центру та правого краю найбільшого паліндрому
        int center = 0;
        int right = 0;

        int maxRadius = 0;
        int maxCenter = 0;

        // Обхід модифікованого рядка
        for (int i = 1; i < radius.length - 1; i++) {
            // Обчислення радіуса поточного символу
            radius[i] = (right > i) ? Math.min(right - i, radius[2 * center - i]) : 0;

            // Розширення паліндрому
            while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < radius.length &&
                    modifiedString.charAt(i - radius[i] - 1) == modifiedString.charAt(i + radius[i] + 1)) {
                radius[i]++;
            }

            // Оновлення найбільшого паліндрому
            if (radius[i] > maxRadius) {
                maxRadius = radius[i];
                maxCenter = i;
            }

            // Оновлення правого краю
            if (i + radius[i] > right) {
                right = i + radius[i];
                center = i;
            }
        }

        // Вилучення найдовшого підрядка-паліндрома
        return modifiedString.substring(maxCenter - maxRadius, maxCenter + maxRadius + 1).replaceAll("#", "");
    }

    public static void main(String[] args) {
        String str = "forgeeksskeegfor";
        System.out.println(findLongestPalindrome(str)); // Виведе: forgeeksskeegfor
        String str2 = "banana";
         System.out.println(findLongestPalindrome(str2)); // Виведе: anana
    }
}

Результат виконання алгоритму

В результаті застосування алгоритму Манакера, ми отримуємо найдовший паліндромний підрядок, присутній у заданому рядку. У наведеному вище прикладі, найбільшим паліндромом є “forgeeksskeegfor”.

Сильні та слабкі сторони алгоритму Манакера

Переваги:

  • Лінійна часова складність O(n), що робить його дуже швидким.
  • Універсальність у виявленні як парних, так і непарних паліндромів.
  • Висока ефективність при роботі з довгими рядками.

Недоліки:

  • Вимагає додаткової пам’яті для зберігання таблиці радіусів.
  • Може здаватися дещо складним для розуміння та реалізації.

Заключні думки

Алгоритм Манакера є цінним інструментом для ефективного пошуку найдовшого паліндромного підрядка в рядку. Його швидкість та надійність роблять його придатним для широкого спектру застосувань у обробці текстів та інших областях. Незважаючи на деякі недоліки, його переваги значно переважають, роблячи його вибором номер один для таких задач.

Питання та відповіді

1. Яка складність за часом у алгоритму Манакера?
– Алгоритм має лінійну часову складність, O(n).

2. Чи здатний алгоритм Манакера ідентифікувати паліндроми, що перекриваються?
– Ні, алгоритм призначений для виявлення найдовшого неперекриваючогося паліндромного підрядка.

3. Чи можна використовувати цей алгоритм для будь-яких текстових рядків?
– Так, він може працювати з рядками, що містять цифри, літери та інші символи.

4. Чи можливо покращити алгоритм Манакера?
– Так, існують модифікації, такі як алгоритм Кнута-Морріса-Пратта (KMP), що можуть виявитися ефективнішими в певних випадках.

5. Чи існують інші методи виявлення найдовших паліндромних підрядків?
– Так, є інші алгоритми, такі як алгоритм Манассе-Мейєра (Manasse-Myers) та алгоритм Гоарса-Шира (Horspool-Shier).

6. Де може бути застосований алгоритм Манакера?
– Він використовується в біоінформатиці для аналізу послідовностей ДНК, в обробці тексту для виявлення паліндромів, і в багатьох інших областях.

7. Чи можна реалізувати алгоритм Манакера на інших мовах програмування?
– Так, його можна реалізувати на C++, Python, C# та багатьох інших мовах.

8. Де можна знайти додаткову інформацію про цей алгоритм?
– Ось корисні ресурси:
Вікіпедія: Алгоритм Манакера
GeeksforGeeks: Алгоритм Манакера
LeetCode: Знайти найдовший підрядок паліндрому