Longest palindromic substrings: Difference between revisions
Content added Content deleted
Alpha bravo (talk | contribs) |
(Added Algol 68) |
||
Line 45: | Line 45: | ||
'drome' -> 'e' |
'drome' -> 'e' |
||
'the abbatial palace' -> 'abba' |
'the abbatial palace' -> 'abba' |
||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
Palindromes of length 1 or more are detected, finds the left most palindrome if there are several of the same length.<br> |
|||
Treats upper and lower case as distinct and does not require the characters to be letters. |
|||
<lang algol68>BEGIN # find the longest palindromic substring of a string # |
|||
# returns the length of s # |
|||
OP LENGTH = ( STRING s )INT: ( UPB s + 1 ) - LWB s; |
|||
# returns s right-padded with blanks to at least w characters or s if it is already wide enough # |
|||
PRIO PAD = 1; |
|||
OP PAD = ( STRING s, INT w )STRING: |
|||
BEGIN |
|||
STRING result := s; |
|||
WHILE LENGTH result < w DO result +:= " " OD; |
|||
result |
|||
END # PAD # ; |
|||
# returns the longest palindromic substring of s # |
|||
# if there are multiple substrings with the longest length, the leftmost is returned # |
|||
PROC longest palindromic substring = ( STRING s )STRING: |
|||
IF INT len = LENGTH s; |
|||
len < 2 |
|||
THEN s |
|||
ELSE |
|||
INT lwb s = LWB s; |
|||
INT upb s = UPB s; |
|||
STRING result := s[ lwb s ]; |
|||
IF s[ lwb s + 1 ] = s[ lwb s ] THEN |
|||
# the first two characters are a palindrome # |
|||
result +:= s[ lwb s + 1 ] |
|||
FI; |
|||
FOR i FROM lwb s + 1 TO upb s - 1 DO |
|||
INT p start := i; |
|||
INT p end := i + 1; |
|||
BOOL have palindrome := FALSE; |
|||
IF s[ i - 1 ] = s[ i + 1 ] THEN |
|||
# odd length palindrome at i - 1 # |
|||
p start := i - 1; |
|||
have palindrome := TRUE |
|||
ELIF s[ i ] = s[ i + 1 ] THEN |
|||
# even length palindrome at i # |
|||
have palindrome := TRUE |
|||
FI; |
|||
IF have palindrome THEN |
|||
# have a palindrome at p start : p end # |
|||
# attempt to enlarge the range # |
|||
WHILE IF p start = lwb s OR p end = upb s |
|||
THEN FALSE |
|||
ELSE s[ p start - 1 ] = s[ p end + 1 ] |
|||
FI |
|||
DO |
|||
# can extend he palindrome # |
|||
p start -:= 1; |
|||
p end +:= 1 |
|||
OD; |
|||
IF STRING new palindrome = s[ p start : p end ]; |
|||
LENGTH new palindrome > LENGTH result |
|||
THEN |
|||
# have a longer palindrome # |
|||
result := new palindrome |
|||
FI |
|||
FI |
|||
OD; |
|||
result |
|||
FI # longest palindromic substring # ; |
|||
# finds the longest palindromic substring of s and checks it is the expacted value # |
|||
PROC test = ( STRING s, expected value )VOID: |
|||
BEGIN |
|||
STRING palindrome = longest palindromic substring( s ); |
|||
print( ( ( """" + s + """" ) PAD 38, " -> ", ( """" + palindrome + """" ) PAD 36 |
|||
, IF palindrome = expected value THEN "" ELSE " NOT " + expected value + " ???" FI |
|||
, newline |
|||
) |
|||
) |
|||
END # test longest palindromic substring # ; |
|||
test( "three old rotators", "rotator" ); |
|||
test( "never reverse", "ever reve" ); |
|||
test( "stable was I ere I saw elbatrosses", "table was I ere I saw elbat" ); |
|||
test( "abracadabra", "aca" ); |
|||
test( "drome", "d" ); |
|||
test( "x", "x" ); |
|||
test( "the abbatial palace", "abba" ); |
|||
test( "", "" ); |
|||
test( "abcc", "cc" ); |
|||
test( "abbccc", "ccc" ) |
|||
END</lang> |
|||
{{out}} |
|||
<pre> |
|||
"three old rotators" -> "rotator" |
|||
"never reverse" -> "ever reve" |
|||
"stable was I ere I saw elbatrosses" -> "table was I ere I saw elbat" |
|||
"abracadabra" -> "aca" |
|||
"drome" -> "d" |
|||
"x" -> "x" |
|||
"the abbatial palace" -> "abba" |
|||
"" -> "" |
|||
"abcc" -> "cc" |
|||
"abbccc" -> "ccc" |
|||
</pre> |
</pre> |
||