[Openmcl-devel] bit string matching

[Lonnie Cumberland]

My fault, I just noticed that I will have to re-code the
implementation as it is based upon Clojure implementation.

and another implementation that I just found as well:

---------------------------------------
(defn gen-char-map-2
  [#^String s]
  (let [len (.length s)]
    (loop [i 0
	   temp-map {}]
      (when (= (rem i 1000) 0)
	(println "i = " i))
      (if (>= i len)
	temp-map
	(let [current-arr (temp-map (.charAt s i))]
	  (recur (inc i) (assoc temp-map (.charAt s i) (conj current-arr i))))))))

(defn palindrome-2? [#^String s end-point start-point]
  (let [len (- end-point start-point)]
    (loop [i start-point
	   j end-point]
      (if (>= i j)
	(do
	  (println "woohoo palindrome:" (.substring s start-point (inc end-point)))
	  (when (> len max-length)                 ;; set the max-length thread-safely?
	    (def max-length len)))
	(when (= (.charAt s i) (.charAt s j))
	  (recur (inc i) (dec j)))))))


(defn find-largest-palindrome-2
  [#^String s]
  (let [my-map (gen-char-map-2 s)]
    (println "my-map done.")
    (doseq [key (keys my-map)]
      (println "current-key =" key)
      (let [my-arr (my-map key)]
	(when (not-empty my-arr)
	  ;; this loop loops for every first:[rest] second:[rest] ...
	  (loop
	      [current (first my-arr)
	       the-rest (rest my-arr)]
	    (when (not-empty the-rest)
	      ;; this loop loops for every first:[rest] first:[third:rest]
first:[fourth:rest] ...
	      (loop
		  [inner-current current
		   inner-rest the-rest]
		(when (not-empty inner-rest)
		  (when (and
			 (> (- inner-current (first inner-rest)) max-length)
			 (= (.charAt s (dec inner-current)) (.charAt s (inc (first inner-rest)))))
		    (palindrome-2? s inner-current (first inner-rest)))
		  (recur inner-current (rest inner-rest))))
	      (when (and
		     (> (- current (first the-rest)) max-length)
		     (= (.charAt s (dec current)) (.charAt s (inc (first the-rest)))))
		(palindrome-2? s current (first the-rest)))
	      (recur (first the-rest) (rest the-rest)))))))))

(def max-length 2)
(find-largest-palindrome-2 source4)
;; (println (gen-char-map-2 source))
----------------------------------

Thanks again and have a great day,
Lonnie



On Wed, Jan 5, 2011 at 8:38 AM, Lonnie Cumberland
<lonnie at biofuelstechnologyinc.com> wrote:
> Greetings All,
>
> Firstly, let me state that this is not any type of homework problem as
> was suggested by Lou earlier. I was namely in the process of seeing if
> a type of "max-palindrome" function already existed so that it would
> same me some time in having to re-code that part.
>
> On the other side, I am running Clozure 1.6 from
> http://ccl.clozure.com/ on a Windows platform as well.
>
> I just came across a couple of implementations, but could not seem to
> get them to run on Clozure ccl.
>
>
> FROM: http://osdir.com/ml/clojure/2010-10/msg00669.html
> -------------------------------------------------------------------
> (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))))
> ------------------------------------------------------------------
>
> Any ideas on this?
>
> Thanks in advance,
> Lonnie
>
> On Tue, Jan 4, 2011 at 5:23 PM, Lou Vanek <lou.vanek at gmail.com> wrote:
>> Sorry, that's n^3 in time, not n^2. Space calc still holds.
>> _______________________________________________
>> Openmcl-devel mailing list
>> Openmcl-devel at clozure.com
>> http://clozure.com/mailman/listinfo/openmcl-devel
>>
>