Longest palindromic substrings: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 11: | Line 11: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
< |
<syntaxhighlight lang="11l">F longest_palindrome(s) |
||
V t = Array(‘^’s‘$’).join(‘#’) |
V t = Array(‘^’s‘$’).join(‘#’) |
||
V n = t.len |
V n = t.len |
||
Line 35: | Line 35: | ||
‘drome’, |
‘drome’, |
||
‘the abbatial palace’] |
‘the abbatial palace’] |
||
print(‘'’s‘' -> '’longest_palindrome(s)‘'’)</ |
print(‘'’s‘' -> '’longest_palindrome(s)‘'’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 48: | Line 48: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">BYTE FUNC Palindrome(CHAR ARRAY s) |
||
BYTE l,r |
BYTE l,r |
||
Line 91: | Line 91: | ||
Test("qwertyuiop") |
Test("qwertyuiop") |
||
Test("") |
Test("") |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_palindromic_substrings.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_palindromic_substrings.png Screenshot from Atari 8-bit computer] |
||
Line 106: | Line 106: | ||
Palindromes of length 1 or more are detected, finds the left most palindrome if there are several of the same length.<br> |
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. |
Treats upper and lower case as distinct and does not require the characters to be letters. |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the longest palindromic substring of a string # |
||
# returns the length of s # |
# returns the length of s # |
||
OP LENGTH = ( STRING s )INT: ( UPB s + 1 ) - LWB s; |
OP LENGTH = ( STRING s )INT: ( UPB s + 1 ) - LWB s; |
||
Line 182: | Line 182: | ||
test( "abcc", "cc" ); |
test( "abcc", "cc" ); |
||
test( "abbccc", "ccc" ) |
test( "abbccc", "ccc" ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 199: | Line 199: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang="rebol">palindrome?: function [str]-> str = join reverse split str |
||
lps: function [s][ |
lps: function [s][ |
||
Line 228: | Line 228: | ||
print [str "->" (0 < size palindromes)? -> join.with:", " palindromes |
print [str "->" (0 < size palindromes)? -> join.with:", " palindromes |
||
-> "X"] |
-> "X"] |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 241: | Line 241: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">LPS(str){ |
||
found := [], result := [], maxL := 0 |
found := [], result := [], maxL := 0 |
||
while (StrLen(str) >= 2 && StrLen(str) >= maxL){ |
while (StrLen(str) >= 2 && StrLen(str) >= maxL){ |
||
Line 271: | Line 271: | ||
output := v output |
output := v output |
||
return output |
return output |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">db = |
||
( |
( |
||
three old rotators |
three old rotators |
||
Line 290: | Line 290: | ||
} |
} |
||
MsgBox % output |
MsgBox % output |
||
return</ |
return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>three old rotators > ["rotator"] |
<pre>three old rotators > ["rotator"] |
||
Line 303: | Line 303: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===Manacher Function=== |
===Manacher Function=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Manacher Function. Nigel Galloway: October 1st., 2020 |
// Manacher Function. Nigel Galloway: October 1st., 2020 |
||
let Manacher(s:string) = let oddP,evenP=Array.zeroCreate s.Length,Array.zeroCreate s.Length |
let Manacher(s:string) = let oddP,evenP=Array.zeroCreate s.Length,Array.zeroCreate s.Length |
||
Line 318: | Line 318: | ||
match (Ʃ+evenP.[Ʃ])>g with true->fGe (Ʃ-evenP.[Ʃ]+1) (Ʃ+evenP.[Ʃ]) (Ʃ+1) |_->fGe n g (Ʃ+1) |
match (Ʃ+evenP.[Ʃ])>g with true->fGe (Ʃ-evenP.[Ʃ]+1) (Ʃ+evenP.[Ʃ]) (Ʃ+1) |_->fGe n g (Ʃ+1) |
||
(fGo 0 -1 0,fGe 0 -1 0) |
(fGo 0 -1 0,fGe 0 -1 0) |
||
</syntaxhighlight> |
|||
</lang> |
|||
===The Task=== |
===The Task=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
let fN g=if g=[||] then (0,0) else g|>Array.mapi(fun n g->(n,g))|>Array.maxBy snd |
let fN g=if g=[||] then (0,0) else g|>Array.mapi(fun n g->(n,g))|>Array.maxBy snd |
||
let lpss s=let n,g=Manacher s in let n,g=fN n,fN g in if (snd n)*2+1>(snd g)*2 then s.[(fst n)-(snd n)..(fst n)+(snd n)] else s.[(fst g)-(snd g)+1..(fst g)+(snd g)] |
let lpss s=let n,g=Manacher s in let n,g=fN n,fN g in if (snd n)*2+1>(snd g)*2 then s.[(fst n)-(snd n)..(fst n)+(snd n)] else s.[(fst g)-(snd g)+1..(fst g)+(snd g)] |
||
let test = ["three old rotators"; "never reverse"; "stable was I ere I saw elbatrosses"; "abracadabra"; "drome"; "the abbatial palace"; ""] |
let test = ["three old rotators"; "never reverse"; "stable was I ere I saw elbatrosses"; "abracadabra"; "drome"; "the abbatial palace"; ""] |
||
test|>List.iter(fun n->printfn "A longest palindromic substring of \"%s\" is \"%s\"" n (lpss n)) |
test|>List.iter(fun n->printfn "A longest palindromic substring of \"%s\" is \"%s\"" n (lpss n)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 340: | Line 340: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 406: | Line 406: | ||
fmt.Printf(" %-13s Length %d -> %v\n", s, len(longest[0]), longest) |
fmt.Printf(" %-13s Length %d -> %v\n", s, len(longest[0]), longest) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 423: | Line 423: | ||
A list version, written out of curiosity. A faster approach could be made with an indexed datatype. |
A list version, written out of curiosity. A faster approach could be made with an indexed datatype. |
||
< |
<syntaxhighlight lang="haskell">-------------- LONGEST PALINDROMIC SUBSTRINGS ------------ |
||
longestPalindromes :: String -> ([String], Int) |
longestPalindromes :: String -> ([String], Int) |
||
Line 480: | Line 480: | ||
where |
where |
||
rjust n c = drop . length <*> (replicate n c ++) |
rjust n c = drop . length <*> (replicate n c ++) |
||
w = maximum (length . xShow <$> xs)</ |
w = maximum (length . xShow <$> xs)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Longest palindromic substrings: |
<pre>Longest palindromic substrings: |
||
Line 496: | Line 496: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
< |
<syntaxhighlight lang="jq">def longestPalindromicSubstring: |
||
length as $len |
length as $len |
||
| if $len <= 1 then . |
| if $len <= 1 then . |
||
Line 524: | Line 524: | ||
| longestPalindromicSubstring as $longest |
| longestPalindromicSubstring as $longest |
||
| " \(.): length \($longest[0]|length) -> \($longest)" |
| " \(.): length \($longest[0]|length) -> \($longest)" |
||
)</ |
)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 540: | Line 540: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">function allpalindromics(s) |
||
list, len = String[], length(s) |
list, len = String[], length(s) |
||
for i in 1:len-1, j in i+1:len |
for i in 1:len-1, j in i+1:len |
||
Line 557: | Line 557: | ||
join(list[findall(x -> length(x) == length(list[end]), list)], "\" or \""), "\"") |
join(list[findall(x -> length(x) == length(list[end]), list)], "\" or \""), "\"") |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
The longest palindromic substring of babaccd is: "bab" or "aba" |
The longest palindromic substring of babaccd is: "bab" or "aba" |
||
Line 568: | Line 568: | ||
===Manacher algorithm=== |
===Manacher algorithm=== |
||
< |
<syntaxhighlight lang="julia"> |
||
function manacher(str) |
function manacher(str) |
||
s = "^" * join(split(str, ""), "#") * "\$" |
s = "^" * join(split(str, ""), "#") * "\$" |
||
Line 593: | Line 593: | ||
"The longest palindromic substring of $teststring is: \"$pal\"") |
"The longest palindromic substring of $teststring is: \"$pal\"") |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
The longest palindromic substring of babaccd is: "aba" |
The longest palindromic substring of babaccd is: "aba" |
||
Line 605: | Line 605: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[ExpandSubsequenceTry, LongestPalindromicSubsequence] |
||
ExpandSubsequenceTry[seq_List, beginpos : {a_, b_}] := |
ExpandSubsequenceTry[seq_List, beginpos : {a_, b_}] := |
||
Module[{len, maxbroaden, last}, |
Module[{len, maxbroaden, last}, |
||
Line 638: | Line 638: | ||
StringJoin@LongestPalindromicSubsequence[Characters["abracadabra"]] |
StringJoin@LongestPalindromicSubsequence[Characters["abracadabra"]] |
||
StringJoin@LongestPalindromicSubsequence[Characters["drome"]] |
StringJoin@LongestPalindromicSubsequence[Characters["drome"]] |
||
StringJoin@LongestPalindromicSubsequence[Characters["the abbatial palace"]]</ |
StringJoin@LongestPalindromicSubsequence[Characters["the abbatial palace"]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>"rotator" |
<pre>"rotator" |
||
Line 649: | Line 649: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
Simple algorithm but working on Unicode code points. |
Simple algorithm but working on Unicode code points. |
||
< |
<syntaxhighlight lang="nim">import sequtils, strutils, unicode |
||
func isPalindrome(s: seq[Rune]): bool = |
func isPalindrome(s: seq[Rune]): bool = |
||
Line 679: | Line 679: | ||
echo str, " → ", "<no palindromic substring of two of more letters found>" |
echo str, " → ", "<no palindromic substring of two of more letters found>" |
||
else: |
else: |
||
echo str, " → ", result.join(", ")</ |
echo str, " → ", result.join(", ")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 692: | Line 692: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
The short one - find all palindromes with one regex. |
The short one - find all palindromes with one regex. |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Longest_palindromic_substrings |
use strict; # https://rosettacode.org/wiki/Longest_palindromic_substrings |
||
Line 705: | Line 705: | ||
pop =~ /(.+) .? (??{reverse $1}) (?{ $best[length $&]{$&}++ }) (*FAIL)/x; |
pop =~ /(.+) .? (??{reverse $1}) (?{ $best[length $&]{$&}++ }) (*FAIL)/x; |
||
keys %{pop @best}; |
keys %{pop @best}; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 717: | Line 717: | ||
</pre> |
</pre> |
||
The faster one - does the million digits of Pi in under half a second. |
The faster one - does the million digits of Pi in under half a second. |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Longest_palindromic_substrings |
use strict; # https://rosettacode.org/wiki/Longest_palindromic_substrings |
||
Line 756: | Line 756: | ||
I, man, am regal - a German am I |
I, man, am regal - a German am I |
||
toot |
toot |
||
Warsaw was raw</ |
Warsaw was raw</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 764: | Line 764: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- demo/rosetta/Longest_palindromic_substrings.exw (plus two older versions)</span> |
<span style="color: #000080;font-style:italic;">-- demo/rosetta/Longest_palindromic_substrings.exw (plus two older versions)</span> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
Line 799: | Line 799: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">longest_palindromes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">longest_palindromes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])})</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 819: | Line 819: | ||
(This version ignores case but allows non-alphanumerics). |
(This version ignores case but allows non-alphanumerics). |
||
< |
<syntaxhighlight lang="python">'''Longest palindromic substrings''' |
||
Line 952: | Line 952: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Longest palindromic substrings: |
<pre>Longest palindromic substrings: |
||
Line 968: | Line 968: | ||
This version regularizes (ignores) case and ignores non alphanumeric characters. It is only concerned with finding the ''longest'' palindromic substrings so does not exhaustively find ''all possible'' palindromes. If a palindromic substring is found to be part of a longer palindrome, it is not captured separately. Showing the longest 5 palindromic substring groups. Run it with no parameters to operate on the default; pass in a file name to run it against that instead. |
This version regularizes (ignores) case and ignores non alphanumeric characters. It is only concerned with finding the ''longest'' palindromic substrings so does not exhaustively find ''all possible'' palindromes. If a palindromic substring is found to be part of a longer palindrome, it is not captured separately. Showing the longest 5 palindromic substring groups. Run it with no parameters to operate on the default; pass in a file name to run it against that instead. |
||
<lang |
<syntaxhighlight lang="raku" line>my @chars = ( @*ARGS[0] ?? @*ARGS[0].IO.slurp !! q:to/BOB/ ) .lc.comb: /\w/; |
||
Lyrics to "Bob" copyright Weird Al Yankovic |
Lyrics to "Bob" copyright Weird Al Yankovic |
||
https://www.youtube.com/watch?v=JUQDzj6R3p4 |
https://www.youtube.com/watch?v=JUQDzj6R3p4 |
||
Line 1,033: | Line 1,033: | ||
} |
} |
||
"{.key} ({+.value})\t{.value.unique.sort}".put for @cpfoa.classify( *.chars ).sort( -*.key ).head(5);</ |
"{.key} ({+.value})\t{.value.unique.sort}".put for @cpfoa.classify( *.chars ).sort( -*.key ).head(5);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Returns the length, (the count) and the list: |
Returns the length, (the count) and the list: |
||
Line 1,053: | Line 1,053: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program finds and displays the longest palindromic string(s) in a given string. */ |
||
parse arg s /*obtain optional argument from the CL.*/ |
parse arg s /*obtain optional argument from the CL.*/ |
||
if s==''|s=="," then s='babaccd rotator reverse forever several palindrome abaracadaraba' |
if s==''|s=="," then s='babaccd rotator reverse forever several palindrome abaracadaraba' |
||
Line 1,078: | Line 1,078: | ||
@= @ $ /*add a palindromic substring to a list*/ |
@= @ $ /*add a palindromic substring to a list*/ |
||
if short then return 1 /*we have found one palindrome. */ |
if short then return 1 /*we have found one palindrome. */ |
||
end /*j*/; return 0 /* " " " some palindrome(s). */</ |
end /*j*/; return 0 /* " " " some palindrome(s). */</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 1,132: | Line 1,132: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
Line 1,161: | Line 1,161: | ||
see "Longest palindromic substrings:" + nl |
see "Longest palindromic substrings:" + nl |
||
see resList |
see resList |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,176: | Line 1,176: | ||
The Phix entry examples have been used. |
The Phix entry examples have been used. |
||
< |
<syntaxhighlight lang="ecmascript">import "/seq" for Lst |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 1,204: | Line 1,204: | ||
var longest = Lst.distinct(longestPalSubstring.call(s)) |
var longest = Lst.distinct(longestPalSubstring.call(s)) |
||
Fmt.print(" $-13s Length $d -> $n", s, longest[0].count, longest) |
Fmt.print(" $-13s Length $d -> $n", s, longest[0].count, longest) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |