Skip to content

Instantly share code, notes, and snippets.

@Netpilgrim

Netpilgrim/gist:1195103

Created September 5, 2011 14:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Netpilgrim/1195103 to your computer and use it in GitHub Desktop.
Save Netpilgrim/1195103 to your computer and use it in GitHub Desktop.
Download ZIP
Generating prefix functions
Raw
gistfile1.clj
(defn gen-prefn
"Generates a function that for input q returns the lengths of the longest
prefix of pattern that is also a suffix of pattern[1..q]."
[pattern]
(let [pattern (vec pattern)
add-entry (fn [[pfn l] q]
(if (= (pattern l) (pattern q))
[(conj pfn [(inc q) (inc l)]) (inc l)]
(if (zero? l)
[(conj pfn [(inc q) 0]) 0]
(recur [pfn (pfn l)] q))))]
(first (reduce add-entry [{1 0} 0] (range 1 (count pattern))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment