[伯俊]パリンドロンを作る

9630 ワード
白駿 アルゴリズム#アルゴリズム# ファリンドロン? Java テキストリンク

質問する


東昊と圭完は212番で文字列を勉強した.圭完はファリン症候群が大好きです法林文字列とは、前から読んで、後ろから読んで、同じ文字列を読むことです.
東昊は葵婉のためにサプライズプレゼントを用意した.東昊は圭完が書いた文字列Sに0以上の文字を追加し、文字列の後ろにパリンdromを作成しようとした.東昊はできるだけ短い文字列を作りたい.
プログラムを書いて、東昊ができる最も短いファリンドロンの長さを出力します.

入力


最初の行は文字列Sを与える.Sはアルファベット小文字のみで構成され、最大長さは50である.

しゅつりょく


1行目に東昊が作れる最短のファリンドロン長を出力します.

コピー例入力1

abab

コピー例出力1

5

に答える

  • ファリン症候群は奇数と偶数に分けることができる.
  • 長さが奇数の場合
  • len-2から、探索[i-J+1][i+J]、

  • 長さが偶数の場合
  • 文字の長さを2で割ると、1が残っていれば+1
    • を加える.
  • len-2から、探索[i-j+1][i+j]、

  • 答えは長さが短い.

    • コード#コード#

    public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] chars = br.readLine().toCharArray();

        int len = chars.length;

        int answer = (len-1) * 2 + 1;

        if (len == 1){
            System.out.println(1);
            return;
        }


        // 홀수일 경우
        loop : for (int i  = len-2 ; i > len/2-1 ; i--){

            for (int j = 1; j + i < len;  j++){
                if (chars[i-j] != chars[i+j]) continue loop;
            }

            answer = Math.min(answer, i * 2 + 1 );
        }


        // 짝수일 경우
        int end = len;
        if (len % 2 == 1) end++;
        loop : for (int i  = len-2 ; i >= end/2-1 ; i--){

            for (int j = 1; j + i < len;  j++){
                if (chars[i-j+1] != chars[i+j]) continue loop;
            }

            answer = Math.min(answer, (i+1)*2) ;
        }

        System.out.println(answer);
    }
}
    エンタープライズ検索エンジン開発のコネクタconnector(八)
    SWEA 1873上の戦地