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

http://qiita.com/Nabetani/items/66806c9dc14a96f2fd42
http://nabetani.sakura.ne.jp/hena/ord14crosscircle/
円周上のCrossing

正直さっぱりわからなかったので諦めて他人の解答を見たのだが、余計わからなかった。
とりあえず1文字追加するごとに増える本数を数え上げるという形式で実装してみたところ、後半の問題が時間がかかりすぎて終わらないという有様に。
どうすればいいんだろう。

<?php
	class CROSSCIRCLE{
		/**
		* 円周上のCrossing
		* @param String 「aabbca1bcb」みたいな文字列
		* @return int 「14」みたいな数値
		*/
		public function get($input){
			// 初期値
			$count = 0;
			
			// 頭からくるくる
			for($i=0; $i<strlen($input)-1; $i++){
				$pos = $i+2;
				// 先に同じ文字が見つかれば
				while(($pos = strpos($input, $input[$i], $pos)) !== false){
					// 該当の文字で左右に区切る
					$c1 = count_chars(substr($input, $i+1, $pos-$i-1), 1);
					$c2 = count_chars(substr_replace($input, '', $i, $pos-$i+1), 1);
					// 左右に同じ文字があれば、文字数の積が交点の数
					foreach($c1 as $key=>$val){
						if(isset($c2[$key])){
							$count += $val*$c2[$key];
						}
					}
					$pos++;
				}
			}
			// 半分
			return $count/2;
		}
	}
	
	// 以下はテスト
	$test = [
		['aabbca1bcb', '14'],
		['111ZZZ', '0'],
		['v', '0'],
		['ww', '0'],
		['xxx', '0'],
		['yyyy', '1'],
		['zzzzz', '5'],
		['abcdef', '0'],
		['abcaef', '0'],
		['abbaee', '0'],
		['abcacb', '2'],
		['abcabc', '3'],
		['abcdabcd', '6'],
		['abcadeabcade', '23'],
		['abcdeedcba', '0'],
		['abcdeaedcba', '8'],
		['abcdeaedcbad', '16'],
		['QQQQXXXX', '2'],
		['QwQQmQXmXXwX', '14'],
		['111222333', '0'],
		['aaAAaA', '4'],
		['121232313', '12'],
		['1ab1b', '1'],
		['abcdefbadcfe', '12'],
		['abxcdefbadcfex', '14'],
		['dtnwtkt', '0'],
		['mvubvpp', '0'],
		['moggscd', '0'],
		['kzkjzpkw', '2'],
		['fbifybre', '1'],
		['rrrfjryki', '1'],
		['wrbbdwsdwtx', '2'],
		['vvucugvxbvgx', '9'],
		['ojkjzyasjwbfjj', '5'],
		['ggffyuxnkyypifff', '5'],
		['vcgtcqlwrepwvkkogl', '4'],
		['xeqtmmgppwcjpcisogxbs', '4'],
		['lukltpeucrqfvcupnpxwmoj', '6'],
		['zpzswlkkoqwwndwpfdpkhtzgtn', '31'],
		['bkfeflagfvluelududqjcvfyvytfw', '45'],
		['rvqbhfmcjjqlpqzulzerxgyowiwrfkmhw', '26'],
		['qyxvpdtoeexbqsethwjwmqszcxxjnsdoeaet', '144'],
		['rjmsgmswhcolmpbhmpncziymydyalrcnevsrespj', '133'],
		['oxetnyjzjbysnwktfwzndlejfndsqeetsnjvsicyjehd', '395'],
		['wzvddnddzogywcqxbyvagbzmsmtcmrrlbnebmvhaemjouaqim', '219'],
		['karhphxcxqgsyorhusbumbqzocuzvnwzwcpxgsksrviihxrgsrhji', '461'],
		['oxgbononhqdxzmkysgijwvxljpaazmgkurkpffeuwywwuyxhyfkicgyzyc', '441'],
		['sdgsrddwsrwqthhdvhrjhgtxwgurgyiygtktgtughtogzaqmcafkljgpniddsvb', '1077'],
		['qemhecchkgzhxmdcsltwhpoyhkapckkkzosmklcvzkiiucrvzzznmhjfcdumuflavxik', '1711'],
		['ffqmsirwpxrzfkbvmmfeptkbhnrvfcywthkwkbycmayhhkgvuyecbwwofwthlmzruphrcujwhr', '2440'],
	];

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

普通に数えた。

まず1文字目の'a'に注目。
次に出てくる'a'を探すと、2文字目の'a'は間に線を引けないのでパス。
次の'a'は6文字目なので、そこで文字列を分解して'abbc'と'1bcb'を得る。
分解した文字のうち、'a'と'1'は片方にしかないので線を引けない。
'c'は左右に1つずつなので交点数は11=1。
'b'は左右に2つずつなので交点数は22=4。
次の'a'は存在しない、これで1文字目の'a'については終了。

次に1文字目の'a'に注目。
とまあ繰り返していって全部の合計を出した。
実行時間は0.1秒以下になった。はやい。

なお、最後の$pos++をwhile条件に突っ込もうとすると何故かWarningが発生します。