http://qiita.com/Nabetani/items/0b56395d4c9e7c64b230
http://nabetani.sakura.ne.jp/hena/ord15subpalin/
回文の発掘
最初=最後の分岐については、こちらの解説を見てから追加しました。
これが無い場合の実行時間は1.2秒、ある場合は実行時間0.12秒です。
PHPはやい。
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はやい。
PR