Longest palindromic substrings: Difference between revisions
Content added Content deleted
(Realize in F#) |
|||
| Line 9: | Line 9: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
=== |
===Manacher Function=== |
||
<lang fsharp> |
<lang fsharp> |
||
// Mahacher Function. Nigel Galloway: October 1st., 2020 |
// Mahacher Function. Nigel Galloway: October 1st., 2020 |
||
let |
let Manacher(s:string) = let oddP,evenP=Array.zeroCreate s.Length,Array.zeroCreate s.Length |
||
let rec fN i g e (l:int[])=match g>=0 && e<s.Length && s.[g]=s.[e] with true->l.[i]<-l.[i]+1; fN i (g-1) (e+1) l |_->() |
let rec fN i g e (l:int[])=match g>=0 && e<s.Length && s.[g]=s.[e] with true->l.[i]<-l.[i]+1; fN i (g-1) (e+1) l |_->() |
||
let rec fGo n g Ʃ=match Ʃ<s.Length with |
let rec fGo n g Ʃ=match Ʃ<s.Length with |
||
| Line 29: | Line 29: | ||
<lang fsharp> |
<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= |
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)) |
||
| Line 43: | Line 43: | ||
A longest palindromic substring of "" is "" |
A longest palindromic substring of "" is "" |
||
</pre> |
</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||