「第15回オフラインリアルタイムどう書くの参考問題」をPHPで解く


http://qiita.com/Nabetani/items/0b56395d4c9e7c64b230
http://nabetani.sakura.ne.jp/hena/ord15subpalin/
回文の発掘

<?php
    class SUBPLAIN{

        /**
        * 回文の発掘
        * @param String 「I_believe_you_can_solve」みたいな文字列
        * @param int 現在の回文長
        * @return int 「9」みたいな数値
        */
        public function get($input, $length=0){
            // 1文字以下であれば終了
            if(( $iLength = strlen($input)) < 2){ return $length+$iLength; }
            // 最初=最後だった場合問答無用でそれが正解
            if($input[0] === $input[strlen($input)-1]){
                return $this->get(substr($input, 1, -1), $length+2);
            }
            // それ以外の場合は全探査が必要
            $maxLength = [];
            // 全文字でくるくる
            for($i=0;$i<$iLength-1; $i++){
                // 該当文字と同じものを後ろからみつける
                $b = strrpos($input, $input[$i]);
                if( $b > $i){
                    // 該当文字と同じものが後ろにある場合、その間の文字で再度回文発掘
                    $maxLength[] = $this->get(substr($input, $i+1, $b-$i-1), $length+2);
                }elseif($b === $i){
                    // 前後から見て同じなので終了
                    $maxLength[] = $length+1;
                }
            }
            // 探索した中で最大長のものを返す
            return max($maxLength);
        }

    }

    // 以下はテスト
    $test = [
        ['1234567890987654321', '19'],
        ['a', '1'],
        ['aa', '2'],
        ['aaa', '3'],
        ['ab', '1'],
        ['aabb', '2'],
        ['ABBA', '4'],
        ['Abba', '2'],
        ['1234567890', '1'],
        ['1234567890987654321', '19'],
        ['abcdcba', '7'],
        ['0a1b2c3d4c5b6a7', '7'],
        ['abcdcba0123210', '7'],
        ['abcdcba_123210', '7'],
        ['_bcdcba0123210', '7'],
        ['abcddcba0123210', '8'],
        ['abcdcba01233210', '8'],
        ['a0bc1dc2ba3210a', '9'],
        ['a0bc1ddc2ba3210', '8'],
        ['3a0bc1ddc2ba3210', '10'],
        ['11oooo1111o1oo1o111ooooooooooo', '20'],
        ['11o1111o1111oo11ooo11111ooo1oo', '20'],
        ['111111oo11o111ooo1o1ooo11ooo1o', '21'],
        ['11o1o1o11oo11o11oo111o1o1o11oo', '27'],
        ['oo111o1o11o1oo1ooo11o1o11o1o1o', '27'],
        ['1o1oo11111o1o1oo1o1o1111oo1o1o', '28'],
        ['QQooooQooooQQyQoyQQQyyyyQQoyoy', '15'],
        ['oQoooQooooQyoyQoyoyyyQQyQQQQoQ', '16'],
        ['yyyyyooyQyyyoyyQyyooyQoQoQQoQy', '17'],
        ['yyQoyQoyyQyQQoyooooyyQQyQyooQy', '24'],
        ['oQQooQoQyQQoyoQQoQyQyQyQoQoooo', '24'],
        ['oQQyQQyyQyQQoooyQQyyyQQQyyQQoy', '25'],
        ['WAk9iHI4jVDlStyudwTNqE138kwan2', '3'],
        ['c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7', '3'],
        ['CAbYcW5VqHjzFdIkH_61PM0TsyRuie', '3'],
        ['jInQnUvSayrJTsQWujovbbqW0STvoj', '10'],
        ['iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG', '11'],
        ['ROgYUOu6er_DA7nB6UGquO1GUHC62R', '11'],
        ['Oh_be_a_fine_girl_kiss_me', '9'],
        ['8086_6502_6809_Z80', '11'],
        ['xcode_visualstudio_eclipse', '11'],
        ['word_excel_powerpoint_outlook', '9'],
        ['abcdefghijklmnopqrstuvwxyz0123', '1'],
    ];

    $subpalin = new SUBPLAIN();
    foreach($test as $key=>$data){
        $answer = $subpalin->get($data[0]);
        if($answer !== (int)$data[1]){
            print('えらー');
        }
    }

どう作ろうか相当考えあぐねていたのですが、全探査でいいやと思い立ったら1時間で終わった。

最初=最後の分岐については、こちらの解説を見てから追加しました。
これが無い場合の実行時間は1.2秒、ある場合は実行時間0.12秒です。
PHPはやい。