lcs.clj

;;; 文字列の指定
(def sentence "mississippi")
(def sentence "Ask not what your country can do for you but what you can do for your country")

;;; 接尾辞リストを作る
(defn tail [x]
  (loop [s x result []]
    (if (empty? s) (conj result s) (recur (apply str (rest s)) (conj result s) ))))

;;; ソートする
(sort (tail sentence))

;;; 隣り合う要素を組みにする
(partition 2 1 (sort (tail sentence)))

;;; 文字列の共通している部分の長さを求める
(defn consensus-seq [s1 s2]
  (apply str (map #(first %) (take-while  #(= (first %) (last %)) (map list s1 s2))) ))

(map #(list (count %) %) (map #(apply consensus-seq %)  (partition 2 1 (sort (tail sentence)))))


;;; 共通部分が一番長い要素を取り出す & 共通部分のみを残す
(defn longest-duplicated-substring [s]
  (first (sort #(< (first %2) (first %1))
             (map #(list (count %) %)
                  (map #(apply consensus-seq %)
                       (partition 2 1 (sort (tail s))))))))


;;; 結果を出力する
(longest-duplicated-substring sentence)