Content deleted Content added
No edit summary |
|||
Line 41:
'''}'''
// 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] != '|', PalindromeRaii[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=PalindromeRaii[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)
| |||