I took a different approach, not wildly "clojurish", type-hinted,
ugly, but also pretty fast. About 1.2ms on my machine (after about 10
runs so the JIT has done its magic).
The approach is to look at each character, or pair of adjacent
characters, as the potential center of a palindrome and then "grow"
the palindrome out from that seed until it looses its palindromness.
Kent.
(def st
"FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth")
(defn longest-palindrome-at [^String st ind1 ind2]
(let [ind1 (int ind1)
ind2 (int ind2)]
(if (= (.charAt st ind1)
(.charAt st ind2))
(if (or (zero? ind1) (= ind2 (dec (.length st))))
[ind1 ind2]
(recur st (dec ind1) (inc ind2)))
[(inc ind1) (dec ind2)])))
(defn longest [^String st]
(let [[ind1 ind2]
(apply max-key (fn [[i1 i2]] (let [i1 (int i1) i2 (int i2)]
(- i2 i1)))
(concat
(for [i (range (.length st))]
(longest-palindrome-at st i i))
(for [i (range 1 (.length st))]
(longest-palindrome-at st (dec i) i))))]
(.substring st ind1 (inc ind2))))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
