「最長繰り返し区間探索問題」

問題の説明

例１：	列 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 つを出力すれば よい．

厳密な定義を最後に与えるので，わからない場合には，その定義を元に検討 して欲しい（課題に対する質問は受け付けない）．以下では，誤解を招きそ うな点を例で説明する．

例２：

列 Y = 001011000000101100001011001011 の中には，部分列 1011 が 繰り返して現れてはいるが，飛び飛びにしか出て来ていない．したが って，1011 は繰り返し列ではない．ちなみに，この列では， 0010110000 が 2 回続いて繰り返されているので，0010110000 が繰り返し 列で，最長繰り返し区間は， 00101100000010110000 である． なお，0001011000010110 と 0000101100001011 は， 位置を１〜２ずらしただけで，同じ最長繰り返し区間となっている． こうしたケースにおいては，それらのどれかを出力すればよい．

例３：	列 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 の繰り返し区間の中で最長のもの

プログラミングに関する補足

1. 文字列数の上限は100,000とする．
2. 解答プログラムは標準入力から文字列を入力し，標準出力に

   
          繰り返し列　最長繰り返し区間長
   

   を出力しなさい．複数候補がある場合はどれか一つを出力すればよい．