TopCoder SRM198 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。

入力の文字列inputが与えられたときに、2回以上同じ文字列が現れる文字列の中で、最長になる文字列の長さを返せ。なお、文字列inputの長さの上限は50であり、文字列に利用可能な文字は小文字、大文字のアルファベットのみとする。

サンプルとなる解答はこちら。

public class Reppity {
 public int longestRep(String input) {
  for( int i=input.length()/2 ; i>0 ; i-- ){
   for( int j=0 ; j<input.length()-i ; j++ ){
    String tar = input.substring(j, j+i);
    if( input.substring(j+i).contains(tar) ) return i;
   }
  }
 return 0;
 }
}

長い方の文字列から探索していくのがキモ。気持ちのよい解き方が思い浮かばず解くのを断念してしまいました。解答を見れば納得できるのですがね...