「第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はやい。
Author And Source
この問題について(「第15回オフラインリアルタイムどう書くの参考問題」をPHPで解く), 我々は、より多くの情報をここで見つけました https://qiita.com/rana_kualu/items/3fb13b95f5b4509fd48a著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .