Longest palindromic substrings: Difference between revisions
Added Easylang
Drkameleon (talk | contribs) (Added Arturo implementation) |
(Added Easylang) |
||
| (6 intermediate revisions by 6 users not shown) | |||
Line 11:
=={{header|11l}}==
<
V t = Array(‘^’s‘$’).join(‘#’)
V n = t.len
Line 35:
‘drome’,
‘the abbatial palace’]
print(‘'’s‘' -> '’longest_palindrome(s)‘'’)</
{{out}}
Line 48:
=={{header|Action!}}==
<
BYTE l,r
Line 91:
Test("qwertyuiop")
Test("")
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_palindromic_substrings.png Screenshot from Atari 8-bit computer]
Line 106:
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.
<
# returns the length of s #
OP LENGTH = ( STRING s )INT: ( UPB s + 1 ) - LWB s;
Line 182:
test( "abcc", "cc" );
test( "abbccc", "ccc" )
END</
{{out}}
<pre>
Line 199:
=={{header|Arturo}}==
{{trans|Nim}}
<
lps: function [s][
Line 228:
print [str "->" (0 < size palindromes)? -> join.with:", " palindromes
-> "X"]
]</
{{out}}
Line 241:
=={{header|AutoHotkey}}==
<
found := [], result := [], maxL := 0
while (StrLen(str) >= 2 && StrLen(str) >= maxL){
Line 271:
output := v output
return output
}</
Examples:<
(
three old rotators
Line 290:
}
MsgBox % output
return</
{{out}}
<pre>three old rotators > ["rotator"]
Line 299:
x > []
the abbatial palace > ["abba"]
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
func$ reverse s$ .
a$[] = strchars s$
for i = 1 to len a$[] div 2
swap a$[i] a$[len a$[] - i + 1]
.
return strjoin a$[]
.
func palin s$ .
if s$ = reverse s$
return 1
.
return 0
.
func$ lpali st$ .
for n = 1 to len st$ - 1
for m = n + 1 to len st$
sub$ = substr st$ n (m - n)
if palin sub$ = 1
if len sub$ > len max$
max$ = sub$
.
.
.
.
return max$
.
for s$ in [ "three old rotators" "never reverse" "stable was I ere I saw elbatrosses" "abracadabra" "drome" "the abbatial palace" ]
print lpali s$
.
</syntaxhighlight>
{{out}}
<pre>
rotator
ever reve
table was I ere I saw elbat
aca
d
abba
</pre>
=={{header|F_Sharp|F#}}==
===Manacher Function===
<
// Manacher Function. Nigel Galloway: October 1st., 2020
let Manacher(s:string) = let oddP,evenP=Array.zeroCreate s.Length,Array.zeroCreate s.Length
Line 318 ⟶ 360:
match (Ʃ+evenP.[Ʃ])>g with true->fGe (Ʃ-evenP.[Ʃ]+1) (Ʃ+evenP.[Ʃ]) (Ʃ+1) |_->fGe n g (Ʃ+1)
(fGo 0 -1 0,fGe 0 -1 0)
</syntaxhighlight>
===The Task===
<
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 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))
</syntaxhighlight>
{{out}}
<pre>
Line 337 ⟶ 379:
A longest palindromic substring of "" is ""
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vbnet">Function isPalindrome(s As String) As Integer
For i As Integer = 1 To Len(s) / 2
If Mid(s, i, 1) <> Mid(s, Len(s) - i + 1, 1) Then Return False
Next i
Return True
End Function
Sub LongestPalindrome(s As String)
Dim As String substr, longest = ""
Dim As Integer i, j
For i = 1 To Len(s)
For j = i To Len(s)
substr = Mid(s, i, j - i + 1)
If isPalindrome(substr) Andalso Len(substr) > Len(longest) Then longest = substr
Next j
Next i
Print "The longest palindromic substring is/are: "
For i = 1 To Len(s)
For j = i To Len(s)
substr = Mid(s, i, j - i + 1)
If IsPalindrome(substr) Andalso Len(substr) = Len(longest) Andalso Len(substr) > 2 Then Print substr; " ";
Next j
Next i
If Len(longest) <= 2 Then Print "<no palindromic substring of two of more letters found>"
End Sub
Dim s As String
Input "Enter a string: ", s
LongestPalindrome(s)
Sleep</syntaxhighlight>
=={{header|Go}}==
{{trans|Wren}}
<
import (
Line 406 ⟶ 483:
fmt.Printf(" %-13s Length %d -> %v\n", s, len(longest[0]), longest)
}
}</
{{out}}
Line 423 ⟶ 500:
A list version, written out of curiosity. A faster approach could be made with an indexed datatype.
<
longestPalindromes :: String -> ([String], Int)
Line 480 ⟶ 557:
where
rjust n c = drop . length <*> (replicate n c ++)
w = maximum (length . xShow <$> xs)</
{{Out}}
<pre>Longest palindromic substrings:
Line 496 ⟶ 573:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<
length as $len
| if $len <= 1 then .
Line 524 ⟶ 601:
| longestPalindromicSubstring as $longest
| " \(.): length \($longest[0]|length) -> \($longest)"
)</
{{out}}
Line 540 ⟶ 617:
=={{header|Julia}}==
<
list, len = String[], length(s)
for i in 1:len-1, j in i+1:len
Line 557 ⟶ 634:
join(list[findall(x -> length(x) == length(list[end]), list)], "\" or \""), "\"")
end
</
<pre>
The longest palindromic substring of babaccd is: "bab" or "aba"
Line 568 ⟶ 645:
===Manacher algorithm===
<
function manacher(str)
s = "^" * join(split(str, ""), "#") * "\$"
Line 593 ⟶ 670:
"The longest palindromic substring of $teststring is: \"$pal\"")
end
</
<pre>
The longest palindromic substring of babaccd is: "aba"
Line 603 ⟶ 680:
The longest palindromic substring of abaracadabra is: "ara"
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[ExpandSubsequenceTry, LongestPalindromicSubsequence]
ExpandSubsequenceTry[seq_List, beginpos : {a_, b_}] :=
Module[{len, maxbroaden, last},
len = Length[seq];
maxbroaden = Min[a - 1, len - b];
last = maxbroaden;
Do[
If[! PalindromeQ[Take[seq, {a - j, b + j}]],
last = j - 1;
Break[];
]
,
{j, maxbroaden}
];
{a - last, b + last}
]
LongestPalindromicSubsequence[l_List] :=
Module[{evenposs, oddposs, subseqs},
evenposs = SequencePosition[l, {x_, x_}];
oddposs = SequencePosition[l, {x_, y_, x_}];
subseqs = Join[evenposs, oddposs];
subseqs = ExpandSubsequenceTry[l, #] & /@ subseqs;
If[Length[subseqs] > 0,
TakeLargestBy[Take[l, #] & /@ subseqs, Length, 1][[1]]
,
{}
]
]
StringJoin@LongestPalindromicSubsequence[Characters["three old rotators"]]
StringJoin@LongestPalindromicSubsequence[Characters["never reverse"]]
StringJoin@LongestPalindromicSubsequence[Characters["stable was I ere I saw elbatrosses"]]
StringJoin@LongestPalindromicSubsequence[Characters["abracadabra"]]
StringJoin@LongestPalindromicSubsequence[Characters["drome"]]
StringJoin@LongestPalindromicSubsequence[Characters["the abbatial palace"]]</syntaxhighlight>
{{out}}
<pre>"rotator"
"ever reve"
"table was I ere I saw elbat"
"aca"
""
"abba"</pre>
=={{header|Nim}}==
Simple algorithm but working on Unicode code points.
<
func isPalindrome(s: seq[Rune]): bool =
Line 636 ⟶ 756:
echo str, " → ", "<no palindromic substring of two of more letters found>"
else:
echo str, " → ", result.join(", ")</
{{out}}
Line 646 ⟶ 766:
tantôt → tôt
étêté → étêté</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
<syntaxhighlight lang="pascal">
program FindLongestPalindrome;
uses
SysUtils,strutils;
const
arr: array of string = ('three old rotators', 'never reverse', 'stable was I ere I saw elbatrosses', 'abracadabra', 'drome', 'the abbatial palace', '');
var
st, longestPalindrome, dummy: string;
i, j, longest: integer;
begin
for st in arr do
begin
longest := 0;
longestPalindrome := '';
for i := 1 to Length(st) do
begin
for j := Length(st) downto i do
begin
dummy := Copy(st, i, j - i + 1);
if (j - i + 1 > longest) and (dummy = ReverseString(dummy)) then
begin
longest := j - i + 1;
longestPalindrome := dummy;
end;
end;
end;
WriteLn(Format('%-35s -> %s', [st, longestPalindrome]));
end;
end.
</syntaxhighlight>
{{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
the abbatial palace -> abba
->
</pre>
=={{header|Perl}}==
The short one - find all palindromes with one regex.
<syntaxhighlight lang="perl">use strict;
use warnings;
Line 662 ⟶ 828:
pop =~ /(.+) .? (??{reverse $1}) (?{ $best[length $&]{$&}++ }) (*FAIL)/x;
keys %{pop @best};
}</
{{out}}
<pre>
Line 673 ⟶ 839:
Longest Palindrome For abaracadabra = aba ara aca ada
</pre>
The faster one - does the million digits of Pi in under half a second.
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'bitwise';
#@ARGV = 'pi.dat'; # uncomment to use this file or add filename to command line
Line 695 ⟶ 861:
my $right = substr $forward, $i, $range;
my $left = substr $backward, $length - $i, $range;
( $right ^. $left ) =~ /^\0\0+/ and # evens
($len = 2 * length $&) >= $#best and
$best[ $len ]{substr $forward, $i - length $&, $len}++;
( $right ^. "\0" . $left ) =~ /^.(\0+)/ and # odds
($len = 1 + 2 * length $1) >= $#best and
$best[ $len ]{substr $forward, $i - length $1, $len}++;
Line 713 ⟶ 879:
I, man, am regal - a German am I
toot
Warsaw was raw</
{{out}}
<pre>
Line 721 ⟶ 887:
=={{header|Phix}}==
{{trans|Raku}}
<!--<
<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>
Line 756 ⟶ 922:
<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>
<!--</
{{out}}
<pre>
Line 776 ⟶ 942:
(This version ignores case but allows non-alphanumerics).
<
Line 909 ⟶ 1,075:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Longest palindromic substrings:
Line 925 ⟶ 1,091:
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.
<syntaxhighlight lang="raku"
Lyrics to "Bob" copyright Weird Al Yankovic
https://www.youtube.com/watch?v=JUQDzj6R3p4
Line 990 ⟶ 1,156:
}
"{.key} ({+.value})\t{.value.unique.sort}".put for @cpfoa.classify( *.chars ).sort( -*.key ).head(5);</
{{out}}
Returns the length, (the count) and the list:
Line 1,010 ⟶ 1,176:
=={{header|REXX}}==
<
parse arg s /*obtain optional argument from the CL.*/
if s==''|s=="," then s='babaccd rotator reverse forever several palindrome abaracadaraba'
Line 1,035 ⟶ 1,201:
@= @ $ /*add a palindromic substring to a list*/
if short then return 1 /*we have found one palindrome. */
end /*j*/; return 0 /* " " " some palindrome(s). */</
{{out|output|text= when using the default input:}}
<pre>
Line 1,089 ⟶ 1,255:
=={{header|Ring}}==
<
load "stdlib.ring"
Line 1,118 ⟶ 1,284:
see "Longest palindromic substrings:" + nl
see resList
</syntaxhighlight>
{{out}}
<pre>
Line 1,133 ⟶ 1,299:
The Phix entry examples have been used.
<
import "./fmt" for Fmt
var longestPalSubstring = Fn.new { |s|
Line 1,161 ⟶ 1,327:
var longest = Lst.distinct(longestPalSubstring.call(s))
Fmt.print(" $-13s Length $d -> $n", s, longest[0].count, longest)
}</
{{out}}
| |||