忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/07/23 19:51 |
PHP5.6.0 「第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はやい。
PR


2014/05/30 23:06 | Comments(0) | PHP

コメント

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<買ったものリスト 2014/06/01 | HOME | PHP5.6.0 「第16回オフラインリアルタイムどう書くの問題」をPHPで解く>>
忍者ブログ[PR]