回文の発掘, saihon2013さんのエレガントな解答を参考に書き直しました。

2013-11-01-palindrome-v2.lisp

;;;; Last modified: 2013-12-13 20:30:09 tkych

;; saihon2013さんのエレガントな解答を参考に書き直しました。


;;====================================================================
;; 回文の発掘 ver.2
;;====================================================================
;; - [回文の発掘 〜 横へな 2013.11.1 参考問題](http://nabetani.sakura.ne.jp/hena/ord15subpalin/)
;; - [第15回オフラインリアルタイムどう書くの参考問題](http://qiita.com/Nabetani/items/0b56395d4c9e7c64b230)
;; - [saihon2013さんの解答: kaibun.c](http://qiita.com/saihon2013/items/c7b8e94371326a621039)
;; - [shiracamusさんの解答: 第15回オフラインリアルタイムどう書くの参考問題をPythonで](http://qiita.com/shiracamus/items/49da2b5e7097892f48c9)


;;--------------------------------------------------------------------
;; Package
;;--------------------------------------------------------------------

(in-package :cl-user)
(defpackage :find-palindrome-v2 (:use :cl))
(in-package :find-palindrome-v2)


;;--------------------------------------------------------------------
;; Main
;;--------------------------------------------------------------------

(defun main (input)
  (labels ((rec (first last num-match)
             (let ((longest num-match))
               (loop :for f :from first :below (length input) :do
                 (loop :for l :downfrom last :to f :do
                   (when (char= (char input f) (char input l))
                     (let ((match (rec (1+ f) (1- l)
                                       (+ num-match (if (= f l) 1 2)))))
                       (when (> match longest)
                         (setf longest match))
                       (return)))))
               longest)))
    (write-to-string
     (rec 0 (1- (length input)) 0))))



#| アルゴリズムの解説

入力文字列を "banana"とすると：

 (main "banana") => "5"


0. first を固定し、first と last が一致するか、`first = last' となるまで、last を1つずつ前に動かす。
   もし、first が文字列の最後に到達したら goto 2.


    first    last  num-match = 0, longest = 0
     |         |
     V         V
     b|a|n|a|n|a

    first   last   num-match = 0, longest = 0
     |       |
     V       V
     b|a|n|a|n|a

     ...


1-0. もし、first と last で一致するものがなく、`first = last' となった場合、first を一つ後ろに動かし、goto 0.


 first last        num-match = 0, longest = 0
     |/
     V 
     b|a|n|a|n|a

    first    last  num-match = 0, longest = 0
       |       |
       V       V
     b|a|n|a|n|a


1-1. もし、first と last が一致したら、first, last を1つずつ内側に動かし、num-match を増やし、goto 0（再帰）.
  （ num-match を増やす際の条件、`first = last' は、いま着目している部分文字列の長さが奇数の場合）。


    first    last  num-match = 2, longest = 0
       |       |
       V       V
     b|a|n|a|n|a


      first  last  num-match = 4, longest = 0
         |   |
         V   V
     b|a|n|a|n|a


      first  last  num-match = 5, longest = 0
          \ /
           V
     b|a|n|a|n|a


  再帰を抜ける際に num-match が longest より大きい場合、longest を num-match に更新する。


      first  last  num-match = 0, longest = 5
       |     |
       V     V
     b|a|n|a|n|a


2. first が最後に到達したら longest を返し終了。


            first  num-match = 0, longest = 5
               |
               V
     b|a|n|a|n|a

|#


;;--------------------------------------------------------------------
;; Tests
;;--------------------------------------------------------------------

(defun =>? (got expected)
  (assert (string= got expected)))


(time
 (progn
   (=>? (main "I_believe_you_can_solve") "9")
   (=>? (main "a") "1")
   (=>? (main "aa") "2")
   (=>? (main "aaa") "3")
   (=>? (main "ab") "1")
   (=>? (main "aabb") "2")
   (=>? (main "ABBA") "4")
   (=>? (main "Abba") "2")
   (=>? (main "1234567890") "1")
   (=>? (main "1234567890987654321") "19")
   (=>? (main "abcdcba") "7")
   (=>? (main "0a1b2c3d4c5b6a7") "7")
   (=>? (main "abcdcba0123210") "7")
   (=>? (main "abcdcba_123210") "7")
   (=>? (main "_bcdcba0123210") "7")
   (=>? (main "abcddcba0123210") "8")
   (=>? (main "abcdcba01233210") "8")
   (=>? (main "a0bc1dc2ba3210a") "9")
   (=>? (main "a0bc1ddc2ba3210") "8")
   (=>? (main "3a0bc1ddc2ba3210") "10")
   (=>? (main "11oooo1111o1oo1o111ooooooooooo") "20")
   (=>? (main "11o1111o1111oo11ooo11111ooo1oo") "20")
   (=>? (main "111111oo11o111ooo1o1ooo11ooo1o") "21")
   (=>? (main "11o1o1o11oo11o11oo111o1o1o11oo") "27")
   (=>? (main "oo111o1o11o1oo1ooo11o1o11o1o1o") "27")
   (=>? (main "1o1oo11111o1o1oo1o1o1111oo1o1o") "28")
   (=>? (main "QQooooQooooQQyQoyQQQyyyyQQoyoy") "15")
   (=>? (main "oQoooQooooQyoyQoyoyyyQQyQQQQoQ") "16")
   (=>? (main "yyyyyooyQyyyoyyQyyooyQoQoQQoQy") "17")
   (=>? (main "yyQoyQoyyQyQQoyooooyyQQyQyooQy") "24")
   (=>? (main "oQQooQoQyQQoyoQQoQyQyQyQoQoooo") "24")
   (=>? (main "oQQyQQyyQyQQoooyQQyyyQQQyyQQoy") "25")
   (=>? (main "WAk9iHI4jVDlStyudwTNqE138kwan2") "3")
   (=>? (main "c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7") "3")
   (=>? (main "CAbYcW5VqHjzFdIkH_61PM0TsyRuie") "3")
   (=>? (main "jInQnUvSayrJTsQWujovbbqW0STvoj") "10")
   (=>? (main "iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG") "11")
   (=>? (main "ROgYUOu6er_DA7nB6UGquO1GUHC62R") "11")
   (=>? (main "Oh_be_a_fine_girl_kiss_me") "9")
   (=>? (main "8086_6502_6809_Z80") "11")
   (=>? (main "xcode_visualstudio_eclipse") "11")
   (=>? (main "word_excel_powerpoint_outlook") "9")
   (=>? (main "abcdefghijklmnopqrstuvwxyz0123") "1")
   ))

;;====================================================================