例1: |
列 X = 111001110011100111001001 を考えてみよう.この列の
4 文字目から 8 文字目までの部分列 00111 は,引き続き,
9 文字目から 13 文字目まで,そしてさらに 14 文字目から
18 文字目まで,連続して 3 回現れている.このような 00111
を繰り返し列といい,4 文字目から 18 文字目までの 15 文字
の部分列を繰り返し区間という.もちろん,4 文字目から
14 文字目までも繰り返し区間である.
なお,この列に対する最長の繰り返し区間は,1 文字目から始 まる 11100 が 4 回繰り返される長さ 20 の区間である. |
プログラムに与える文字列は 0 と 1 の列に限るが,入力部分を簡単にする ために,最後に列の終わりを表わす数字 2 を付け加えたものを問題文字列 とする.解答プログラムは標準入力から問題文字列を入力し,標準出力に繰 り返し列,最長繰り返し区間の長さ,を出力するように作成すること.なお 最長繰り返し区間が 2 つ以上ある場合には,そのうちの 1 つを出力すれば よい.
厳密な定義を最後に与えるので,わからない場合には,その定義を元に検討 して欲しい(課題に対する質問は受け付けない).以下では,誤解を招きそ うな点を例で説明する.
例2: |
列 Y = 001011000000101100001011001011 の中には,部分列 1011 が
繰り返して現れてはいるが,飛び飛びにしか出て来ていない.したが
って,1011 は繰り返し列ではない.ちなみに,この列では,
0010110000 が 2 回続いて繰り返されているので,0010110000 が繰り返し
列で,最長繰り返し区間は, 00101100000010110000 である.
なお,0001011000010110 と 0000101100001011 は, 位置を1〜2ずらしただけで,同じ最長繰り返し区間となっている. こうしたケースにおいては,それらのどれかを出力すればよい. |
例3: | 列 Z = 0101010101111000 では,0101 が繰り返し列になっている. けれども,その場合の繰り返し区間は 01010101 で,長さは 8.一方 01 が繰り返し列になっていると見ることもできる.その場合には, 繰り返し区間は 0101010101 で長い.したがって,この列の場合, 繰り返し列 01 で,最長繰り返し区間長 10 が正解. |
W の部分列 = ある i, j, 1 <= i <= j <= n に対して w[i..j] となる文字列のこと. W の繰り返し列 = W の部分列 w[i..j] で, w[i..j] = w[j+1..j+m] となる列のこと. ただし,m = j - i + 1.つまり,w[i..j] の長さ. W の繰り返し区間 = W の部分列 w[i..k] で,ある繰り返し列 w[i..j] に対し,w[i..k] = w[i..j]...w[i..j] となっているもの.ただし,... の部分は w[i..j] の 0 回以上の繰り返し. W の最長繰り返し区間 = W の繰り返し区間の中で最長のもの
繰り返し列 最長繰り返し区間長を出力しなさい.複数候補がある場合はどれか一つを出力すればよい.
なお,添付ファイルの形式は,
http://www.ring.gr.jp/pub/linux/Vine/Vine-2.6/i386/
http://www.cygwin.com/ http://www.microsoft.com/japan/windows/sfu/
応募受理確認の際に,応募プログラムが評価環境において コンパイルできたかどうかをあわせて回答いたします. 応募プログラムが評価環境でコンパイルできるかどうか 確かめたい場合,応募締め切りに余裕を持って応募する ようにしてください.