Longest palindromic substring: Difference between revisions

Revision as of 12:10, 20 September 2023

Revision as of 05:22, 3 October 2023

Line 63:

Longest_Palindrome(string S, string S') {

// S'The ==algorithm Srequires withan aodd-length bogus character (egstring. '|') inserted

// betweenIt eachcan characterbe (includingshown outerthat boundaries)without loss of generality

// an odd-length string S' can be created from S

// by inserting a distinct character (e.g. '|')

// at the start, at the end as well as between all

// characters of S:

// - odd-length S gets even number of '|', thus S' remains odd-length

// - even-length S gets odd number of '|', thus S' becomes odd-length

// A palindrome in S remains a palindrome in S' and

// extra characters in S' can be trivially accounted for.

// The radius of the longest palindrome centered on each place in S'