Самая длинная палиндромная подстрока

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

Манахер (1975) изобрел $O(n)$ Алгоритм времени для перечисления всех палиндромов, которые появляются в начале строки заданной длины $n$ . Однако, как заметили, например, Апостолико, Бреслауер и Галил (1995) , тот же алгоритм можно использовать и для поиска всех максимальных палиндромных подстрок в любом месте входной строки, опять же в $O(n)$ время. Таким образом, он обеспечивает $O(n)$ -временное решение задачи о самой длинной палиндромной подстроке. Альтернатива $O(n)$ -временные решения были предоставлены Jeuring (1994) и Gusfield (1997) , которые описали решение, основанное на суффиксных деревьях . Более быстрый алгоритм может быть достигнут в модели вычислений со словным ОЗУ , если размер $\sigma$ входного алфавита находится в $2^{o(\log n)}$ . В частности, этот алгоритм работает в $O(n\log \sigma /\log n)$ время использования $O(n\log \sigma /\log n)$ космос. ^[1] эффективные параллельные алгоритмы . Для решения этой задачи также известны ^[2]

Задачу о самой длинной палиндромной подстроке не следует путать с другой проблемой поиска самой длинной палиндромной подпоследовательности .

Более медленный алгоритм

Этот алгоритм медленнее, чем алгоритм Манахера, но является хорошей отправной точкой для понимания алгоритма Манахера. Он рассматривает каждый символ как центр палиндрома и выполняет цикл для определения самого большого палиндрома с этим центром.

Цикл в центре функции работает только для палиндромов, длина которых является нечетным числом. Функция работает с палиндромами четной длины, изменяя входную строку. Символ '|' вставляется между каждым символом входной строки и на обоих концах. Таким образом, входная «книга» становится «|b|o|o|k|». Палиндром четной длины «oo» в слове «book» становится палиндромом нечетной длины «|o|o|».

    Longest_Palindrome_SLOW(string S, string S') {
        // S' == S with a bogus character (eg. '|') inserted 
        // between each character (including outer boundaries)

        // The radius of the longest palindrome centered on each place in S'
        // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1

        array PalindromeRadii = [0,...,0]
        
        Center = 0

        while Center < length(S') {
            // Determine the longest palindrome starting 
            // at Center-Radius and going to Center+Radius
            Radius = 0

            while Center-(Radius + 1) >= 0 and 
                  Center+(Radius + 1) < length(S') and 
                  S'[Center-(Radius + 1)] = S'[Center+(Radius + 1)] {
                Radius = Radius + 1
            }
            
            // Save the radius of the longest palindrome in the array

            PalindromeRadii[Center] = Radius
            
            Center = Center + 1
        }   
                 
        // One can show that longest_palindrome_in_S is max(PalindromeRadii).
        // if S'[i] == '|', PalindromeRadii[i] is even, otherwise you could increase PalindromeRadii[i] by 1,
        // which is equivalent to inserting an extra '|' in each border.
        // Remember that a palindrome centered in an '|' in S' corresponds to an even palindrome in S.
        // if S'[i] != '|', PalindromeRadii[i] is odd (same argument), and corresponds to an odd palindrome.
        // In this case, the length of the palindrome
        // centered at that character is also x=PalindromeRadii[i], as we have (x-1)/2 characters on each side,
        // plus the extra middle one ((x-1)/2*2+1=x)
        longest_palindrome_in_S = max(PalindromeRadii)

        return longest_palindrome_in_S 
    }

Время выполнения этого алгоритма $O(n^{2})$ . Внешний цикл выполняется $n$ раз, а внутренний цикл может выполняться до $n/2$ раз.

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

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

Например, рассмотрим входную строку «абакаба». К тому времени, как он дойдет до «c», алгоритм Манахера определит длину каждого палиндрома, центрированного по буквам перед «c». В точке «c» выполняется цикл для определения самого большого палиндрома с центром в букве «c»: «абакаба». С этим знанием все, что находится после «с», выглядит как отражение всего, что находится до «с». «А» после «С» имеет такой же самый длинный палиндром, как и «А» перед «С». Точно так же буква «b» после «c» имеет самый длинный палиндром, который по крайней мере равен длине самого длинного палиндрома с центром в «b» перед «c». Есть некоторые особые случаи, которые следует учитывать, но этот трюк значительно ускоряет вычисления. ^{[ нужна ссылка ]}

    Longest_Palindrome(string S, string S') {
        // S' == S with a bogus character (eg. '|') inserted 
        // between each character (including outer boundaries)

        // The radius of the longest palindrome centered on each place in S'
        // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1

        array PalindromeRadii = [0,...,0]
        
        Center = 0
        Radius = 0
        
        while Center < length(S') {
	    // At the start of the loop, Radius is already set to a lower-bound
	    // for the longest radius. In the first iteration, Radius is 0, but
	    // it can be higher on later iterations.
            
	    // Determine the longest palindrome starting at Center-Radius and
	    // going to Center+Radius

            while Center-(Radius+1) >= 0 and 
	          Center+(Radius+1) < length(S') and 
		  S'[Center-(Radius+1)] = S'[Center+(Radius+1)] {
                Radius = Radius+1
            }             
         
            // Save the radius of the longest palindrome in the array
            PalindromeRadii[Center] = Radius
            
            // Below, Center is incremented.
            // If any precomputed values can be reused, they are.
            // Also, Radius may be set to a value greater than 0
            
            OldCenter = Center
            OldRadius = Radius
            Center = Center+1

	    // Radius' default value will be 0, if we reach the end of the
	    // following loop. 
            Radius = 0 

            while Center <= OldCenter + OldRadius {

		// Because Center lies inside the old palindrome and every
		// character inside a palindrome has a "mirrored" character
		// reflected across its center, we can use the data that was
		// precomputed for the Center's mirrored point. 

                MirroredCenter = OldCenter - (Center - OldCenter)
                MaxMirroredRadius = OldCenter + OldRadius - Center

                if PalindromeRadii[MirroredCenter] < MaxMirroredRadius {

		    // The palindrome centered at MirroredCenter is entirely
		    // contained in the palindrome centered at OldCenter So,
		    // MirroredCenter and Center have the same sized palindrome

                    PalindromeRadii[Center] = PalindromeRadii[MirroredCenter]
                    Center = Center+1
                } else if PalindromeRadii[MirroredCenter] > MaxMirroredRadius {
                
		    // The palindrome at MirroredCenter extends beyond the
		    // palindrome at OldCenter The palindrome at Center must
		    // end at the edge of the OldCenter palindrome Otherwise,
		    // the palindrome at OldCenter would be bigger

                    PalindromeRadii[Center] = MaxMirroredRadius
                    Center = Center+1
                } else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius

		    // Since the palindrome at MirroredCenter ends exactly at
		    // the edge of the palindrome centered at OldCenter, the
		    // palindrome at Center might be bigger Set Radius to the
		    // minimum size of the palindrome at Center so it doesn't
		    // recheck unnecessarily 

                    Radius = MaxMirroredRadius
                    break
                }   
            }      
        }

	// A palindrome's size is equal to its radius * 2. However, since our
	// variable Radius considers our bogus characters to the side of the
	// center, the size of its corresponding palindrome is actually 2 *
	// (Radius / 2), which means a palindrome's size is equal to its
	// corresponding Radius value in PalindromeRadii

        longest_palindrome_in_S = max(PalindromeRadii)
        return longest_palindrome_in_S
    }

Особые случаи

Алгоритм Манахера работает быстрее, поскольку он повторно использует предварительно вычисленные данные, когда палиндром существует внутри другого палиндрома. Таких случаев 3. Они представлены оператором «if/else if/else» в псевдокоде.

Первый случай — когда палиндром в MirroredCenter полностью лежит внутри «Старого» палиндрома. В этой ситуации палиндром в Center будет иметь ту же длину, что и тот, что в MirroredCenter. Например, если «старый» палиндром — это «abcbpbcba», мы видим, что палиндром с центром на «c» после «p» должен иметь ту же длину, что и палиндром с центром на «c» перед «p».

Второй случай — когда палиндром в MirroredCenter выходит за пределы «Старого» палиндрома. То есть он простирается «влево» (или содержит символы с более низким индексом, чем любой другой внутри «старого» палиндрома). Поскольку «Старый» палиндром — это самый большой из возможных палиндромов с центром в OldCenter, мы знаем, что символы до и после него разные. Таким образом, палиндром в Center будет доходить ровно до границы «Старого» палиндрома, поскольку следующий символ будет отличаться от того, что находится внутри палиндрома в точке MirroredCenter. Например, если строка была «ababc», «Старый» палиндром мог бы быть «bab» с Center будучи вторым «б» и MirroredCenter быть первой буквой «б». Поскольку палиндром в MirroredCenter является «аба» и выходит за границы «Старого» палиндрома, мы знаем, что самый длинный палиндром во второй «b» может простираться только до границы «Старого» палиндрома. Мы знаем это, потому что если бы символом после «Старого» палиндрома была «а» вместо «в», «Старый» палиндром был бы длиннее.

Третий и последний случай — когда палиндром в MirroredCenter простирается ровно до границы «Старого» палиндрома. В этом случае мы не знаем, может ли персонаж после «Старого» палиндрома составить палиндром в Center длиннее, чем тот, что в MirroredCenter. Но мы знаем, что палиндром в Center такой же по крайней мере длины, как тот, что в MirroredCenter. В этом случае, Radius инициализируется радиусом палиндрома в точке MirroredCenter и поиск начинается оттуда. Примером строки может быть «abcbpbcbp», где «старый» палиндром — «bcbpbcb», а Center находится на втором «с». MirroredCenter это первая буква «c», и у нее самый длинный палиндром «bcb». Самый длинный палиндром Center вторая буква «c» должна быть как минимум такой же длины, а в данном случае — длиннее.

Время выполнения

Алгоритм работает за линейное время. В этом можно убедиться, заметив, что Center строго увеличивается после каждого внешнего цикла и сумма Center + Radius не убывает. При этом количество операций в первом внутреннем цикле линейно возрастает по возрастанию суммы Center + Radius в то время как количество операций во втором внутреннем цикле линейно пропорционально увеличению Center. С Center ≤ 2n+1 и Radius ≤ n, общее количество операций в первом и втором внутренних циклах равно $O(n)$ и общее количество операций во внешнем цикле, кроме операций во внутренних циклах, также равно $O(n)$ . Таким образом, общее время работы $O(n)$ .

Примечания

^ Харалампопулос, Панайотис; Писсис, Солон П.; Радошевский, Якуб (июнь 2022 г.). Баннаи, Хидео; Голуб, Ян (ред.). Самая длинная палиндромная подстрока за сублинейное время . Комбинаторное сопоставление с образцом. Международные труды Лейбница по информатике (LIPIcs). Том. 223. Замок Дагштуль. дои : 10.4230/LIPIcs.CPM.2022.20 . Здесь: Теорема 1, п.20:2.
^ Crochemore & Rytter (1991) , Apostolico, Breslauer & Galil (1995) .

См. также

Палиндромное дерево

Ссылки

Апостолико, Альберто; Бреслауер, Дэни; Галил, Цви (1995), «Параллельное обнаружение всех палиндромов в строке» , Theoretical Computer Science , 141 (1–2): 163–173, doi : 10.1016/0304-3975(94)00083-U .
Харалампопулос, Панайотис; Писсис, Солон П.; Радошевски, Якуб (2022), «Самая длинная палиндромная подстрока в сублинейном времени», 33-й ежегодный симпозиум по комбинаторному сопоставлению шаблонов, CPM 2022, 27–29 июня 2022 г., Прага, Чешская Республика , 223 : 20:1–20:9, doi : 10.4230/LIPIcs.CPM.2022.20 .
Крошмор, Максим; Риттер, Войцех (1991), «Полезность алгоритма Карпа-Миллера-Розенберга в параллельных вычислениях над строками и массивами», Theoretical Computer Science , 88 (1): 59–82, doi : 10.1016/0304-3975(91)90073 -Б , МР 1130372 .
Крошмор, Максим; Риттер, Войцех (2003), «8.1 Поиск симметричных слов», «Жемчужины стрингологии: текстовые алгоритмы» , World Scientific, стр. 111–114, ISBN 978-981-02-4897-0 .
Гасфилд, Дэн (1997), «9.2 Поиск всех максимальных палиндромов за линейное время», Алгоритмы для строк, деревьев и последовательностей , Кембридж: Cambridge University Press, стр. 197–199, doi : 10.1017/CBO9780511574931 , ISBN 0-521-58519-8 , МР 1460730 .
Жеуринг, Йохан (1994), «Вывод онлайн-алгоритмов с применением к поиску палиндромов», Algorithmica , 11 (2): 146–184, doi : 10.1007/BF01182773 , hdl : 1874/20926 , MR 1272521 , S2CID 7032332 .
Манахер, Гленн (1975), «Новый «онлайн»-алгоритм с линейным временем для поиска наименьшего начального палиндрома строки», Journal of the ACM , 22 (3): 346–351, doi : 10.1145/321892.321896 , S2CID 10615419 .
В эту статью включен текст самой длинной палиндромной подстроки, доступный по лицензии CC BY 3.0 .

Внешние ссылки

Самая длинная палиндромная подстрока. Часть II. , 20 ноября 2011 г., заархивировано из оригинала 08 декабря 2018 г. Описание алгоритма Манахера для поиска самой длинной палиндромной подстроки за линейное время.
Акалин, Фред (28 ноября 2007 г.), Поиск самой длинной палиндромной подстроки за линейное время , получено 1 октября 2016 г. Объяснение и реализация на Python алгоритма линейного времени Манахера.
Джуринг, Йохан (2007–2010), Палиндромы , получено 22 ноября 2011 г. Реализация на Haskell алгоритма линейного времени Жёринга.
Палиндромы (мертвая ссылка). Java-реализация алгоритма линейного времени Манахера.

[CPR22-1] Харалампопулос, Панайотис; Писсис, Солон П.; Радошевский, Якуб (июнь 2022 г.). Баннаи, Хидео; Голуб, Ян (ред.). Самая длинная палиндромная подстрока за сублинейное время . Комбинаторное сопоставление с образцом. Международные труды Лейбница по информатике (LIPIcs). Том. 223. Замок Дагштуль. дои : 10.4230/LIPIcs.CPM.2022.20 . Здесь: Теорема 1, п.20:2.

[2] Crochemore & Rytter (1991) , Apostolico, Breslauer & Galil (1995) .

[1]

[2]