WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

В разделе компьютерные науки, задача о самой длинной палиндромиальной подстроке — это задача отыскания самой длинной подстроки данной строки являющейся палиндромом. Например, самая длинная палиндромиальная подстрока «банана» это «анана». Самая длинная палиндромиальная подстрока не обязательно единственна; например в строке «абракадабра» нет палиндромиальной подстроки длиннее трёх символов, но есть состоящие в точности из трёх символов, а именно, «ака» и «ада». В некоторых приложениях требуется найти все максимальные палиндромиальные подстроки (а именно, все подстроки, которые сами по себе являются палиндромами и не могут быть дополнены до более длинных палиндромиальных подстрок) вместо того чтобы вернуть только одну подстроку или вернуть максимальную длину палиндромиальной подстроки.

Manacher (1975) открыл линейный по времени алгоритм перечисления всех палиндромов находящихся в начале данной строки. Однако, как было показано Apostolico, Breslauer & Galil (1995), этот же алгоритм может быть использован для нахождения всех самых длинных палиндромиальных подстрок в любом месте данной строки, опять-таки за линейное время. Поэтому он обеспечивает решение задачи нахождения максимальной палиндромиальной подстроки за линейное время. Альтернативные решения, работающие за линейное время, были предложены Jeuring (1994), и Gusfield (1997), который описал решение основанное на использовании суффиксных деревьев. Также известны эффективные параллельные алгоритмы решения этой задачи.[1]

Задачу нахождения самой длинной палиндромиальной подстроки не следует путать с задачей нахождения самой длинной палиндромиальной подпоследовательности.

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

Чтобы за линейное время найти в строке самый длинный палиндром, алгоритм может воспользоваться следующими свойствами палиндромов и подпалиндромов:

  1. Левая часть палиндрома является зеркальным отражением его правой части
  2. (Случай 1) Третий палиндром, чей центр лежит в правой части первого палиндрома, будет иметь в точности ту же длину, что и второй палиндром, центр которого зеркально отражен в левую часть, если второй палиндром лежит внутри первого, отступая от границы по крайней мере на один символ.
  3. (Случай 2) Если второй палиндром имеет общую границу с первым палиндромом, или простирается за его пределы, то длина третьего палиндрома гарантировано не меньше расстояния от его центра до правой границы первого палиндрома. Эта длина совпадает с расстоянием от центра второго палиндрома до самого левого символа первого палиндрома.
  4. Чтобы найти длину третьего палиндрома в случае 2, необходимо сравнивать символы, идущие за самым правым символом первого палиндрома с их зеркальным отражением относительно центра третьего палиндрома пока либо не исчерпается строка, либо не будет обнаружено неравенство символов.
  5. (Случай 3) Ни первый, ни второй палиндромы не предоставляют информации, позволяющей определить длину четвёртого палиндрома, чей центр лежит за границей первого палиндрома.
  6. Поэтому для определения слева направо палиндромиальных длин подстрок в строке желательно иметь опорный палиндром (исполняющий роль первого палиндрома), чьи символы занимают самые правые положения в строке (и, следовательно, третий палиндром в случае 2 и четвёртый палиндром в случае 3 могут заменять первый палиндром, чтобы стать новым опорным палиндромом).
  7. Что касается оценки времени определения палиндромиальный длины для каждого символа строки: в Случае 1 сравнения символов не производится, в Случаях 2 и 3 кандидатами для сравнения являются только символы строки, лежащей за самым правым символом опорного палиндрома (и следовательно Случай 3 всегда приводит к смене опорного палиндрома, когда Случай 2 меняет опорный палиндром только если оказывается что длина третьего палиндрома в действительности больше чем его обещанная минимальная длина).
  8. Для палиндромов чётной степени центр лежит между двумя центральными символами палиндрома.

Реализация

Пусть:

  • s — строка из N символов
  • s2 — производная от s строка, состоящая из N * 2 + 1 элементов, при этом каждый элемент соответствует одному из: N символам в s, N-1 промежутку между символами и границами, и промежуткам, идущим перед первым и за последним символами строки s соответственно
  • Границы в s2 ничем не отличаются друг от друга в плане нахождения длины палиндрома
  • Пусть p будет массивом радиусов палиндрома, то есть расстоянием от центра до любого из самых дальних символов палиндрома (то есть палиндром длиной 3 имеет палиндромиальный радиус 1)
  • Пусть c будет положением центра палиндрома содержащего символ, ближайший к правому концу s2 (длина этого палиндрома p[c]*2+1)
  • Пусть r будет положением самой правой границы этого палиндрома (то есть, r = c + p[c])
  • Пусть i — положение элемента (то есть промежутка или символа) в s2, чей палиндромиальный радиус определяется, причём i всегда расположено правее c
  • Пусть i2 будет зеркальным отражением i относительно c (то есть, {i, i2} = {6, 4}, {7, 3}, {8, 2},… когда c = 5 (значит, i2 = c * 2 — i))
//некорректно работает
import java.util.Arrays;

public class ManachersAlgorithm {
    
    public static String findLongestPalindrome(String s) {
        if (s==null || s.length()==0)
            return "";
        
        char[] s2 = addBoundaries(s.toCharArray());
        int[] p = new int[s2.length]; 
        int c = 0, r = 0; // Here the first element in s2 has been processed.
        int m = 0, n = 0; // The walking indices to compare if two elements are the same
        for (int i = 1; i<s2.length; i++) {
            if (i>r) {
                p[i] = 0; m = i-1; n = i+1;
            } else {
                int i2 = c*2-i;
                if (p[i2]<(r-i)) {
                    p[i] = p[i2];
                    m = -1; // This signals bypassing the while loop below. 
                } else {
                    p[i] = r-i;
                    n = r+1; m = i*2-n;
                }
            }
            while (m>=0 && n<s2.length && s2[m]==s2[n]) {
                p[i]++; m--; n++;
            }
            if ((i+p[i])>r) {
                c = i; r = i+p[i];
            }
        }
        int len = 0; c = 0;
        for (int i = 1; i<s2.length; i++) {
            if (len<p[i]) {
                len = p[i]; c = i;
            }
        }
        char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
        return String.valueOf(removeBoundaries(ss));
    }
 
    private static char[] addBoundaries(char[] cs) {
        if (cs==null || cs.length==0)
            return "||".toCharArray();

        char[] cs2 = new char[cs.length*2+1];
        for (int i = 0; i<(cs2.length-1); i = i+2) {
            cs2[i] = '|';
            cs2[i+1] = cs[i/2];
        }
        cs2[cs2.length-1] = '|';
        return cs2;
    }

    private static char[] removeBoundaries(char[] cs) {
        if (cs==null || cs.length<3)
            return "".toCharArray();

        char[] cs2 = new char[(cs.length-1)/2];
        for (int i = 0; i<cs2.length; i++) {
            cs2[i] = cs[i*2+1];
        }
        return cs2;
    }    
}

Примечания

Литература

Ссылки

This article incorporates text from Longest palindromic substring on PEGWiki under a Creative Commons Attribution (CC-BY-3.0) license.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2020
WikiSort.ru - проект по пересортировке и дополнению контента Википедии