どう書く.orgのトピックから

問題

与えられた文字列内の連続する3文字が，JOIまたはIOIという並びになっている個所がそれぞれ何個所あるのかを数え上げるプログラムを作成せよ．文字列はアルファベットの大文字だけからなる．例えば下図の「JOIOIOI」という文字列にはJOIが1個所，IOIが2個所に含まれている．

第７回日本情報オリンピック　予選２

既に投稿されている回答は、入力を一気に読むものが多かったので、1文字づつ読んでいく方針で解きました。

1文字づつ読んでいく方針の場合、何文字目までマッチしたかというカーソルを保存しておかなければならないので、それを関数のレキシカル環境に保存するようにしてみました。カーソルを保存しておく関数は、make-checkerで作成します。make-checkerで作成された関数は、1文字を引数として受けて、検索文字列のカーソル位置にマッチしなければ nil を、マッチしたら t を返します。ただし検索文字列の最後までマッチした場合は、グローバルの *hit-words* にマッチした文字列を追加し nil を返します。この関数の戻り値は、この関数が不要かどうかを返しています。nil を返した関数は、removeで消される運命になります。

入力に与えられた文字に対して次々に、make-checkerで作成された関数を適応していくという方針です。

投稿したコードです。(ちょっと改良しました)

(defparameter *hit-words* nil)
(defconstant *joi* "JOI")
(defconstant *ioi* "IOI")
(defun make-checker (word)
(let ((cursor 0)
(len (length word)))
#'(lambda (c)
(and (eq (aref word cursor) c)
(incf cursor)
(if (eq cursor len)
(prog1 nil (push word *hit-words*)) ;完全にhitしたら*hit-words*に入れてnilを返す。
t)))))
(loop for c = (read-char)
with checkers = nil
until (eq c #\Newline)
do (push (make-checker *joi*) checkers)
(push (make-checker *ioi*) checkers)
(setq checkers (remove nil
(mapcar
#'(lambda (fn)
(if (funcall fn c) fn))
checkers))))
(format t "~d~%~d~%"
(count *joi* *hit-words* :test 'equal)
(count *ioi* *hit-words* :test 'equal))

入力文字数 × 2 回、make-checker が実行されるし(マッチしなければ作られた関数はすぐ消えるけど)、リストを何回も作りなおしてるので、あまりよくないかもしれません。

でも、自分にしては奇抜なことをやってみたので、楽しかった。

情報オリンピック2007年度国内予選問題は、いい問題が多いなー