AtCoder 練習問題 ABC049C - 白昼夢 通るコードと通らないコードの違いがわかりません

Question

ABC049C - 白昼夢

通らなかったコード

<?php
fscanf(STDIN,'%s',$s);
echo preg_match('/^(dream(er)?|eraser?)*$/',$s)?'YES':'NO';

通ったコード

<?php
fscanf(STDIN,'%s',$s);

function is_possible($s,$words){
	$texts=[$s];
	while(is_array($texts)){
		$texts=get_possibles($texts,$words);
	}
	return $texts;
}
function get_possibles($texts,$words){
	$flags=[];
	foreach($texts as $text){
		foreach($words as $word){
			if($text===$word){return true;}
			$l=strlen($word);
			if(substr($text,0,$l)===$word){
				$flags[substr($text,$l)]=true;
			}
		}
	}
	if(empty($flags)){return false;}
	return array_keys($flags);
}
echo is_possible($s,['dream','dreamer','erase','eraser'])?'YES':'NO';

どちらも入力された文字列が'dream','dreamer','erase','eraser'の組み合わせで構成されているかを検証する処理をしていると思うのですが、なぜ正規表現のパターンが通らないのかわかりません。
正規表現のパターンでも、PHPは内部的にはおおよそ通ったコードと同様に、左から総当たりのようなことをすると思っていたのですが、違うのでしょうか？
正規表現のパターンが誤判定をしてしまう入力はどういうものなのでしょうか？

Comments

[melian]

手元の環境の PHP 8.1.2 では、"dream" を 10,000回繰り返す文字列(50,000文字)を入力すると "NO" が返ります。

$ yes dream | head -n 10000 | xargs | tr -d ' ' | php daydream.php
NO

同じ正規表現を GNU Awk で使用すると "YES" になります。

$ yes dream | head -n 10000 | xargs | tr -d ' ' | awk '/^(dream(er)?|eraser?)*$/{print "YES";exit}{print "NO"}';
YES

[Zuishin]

pcre.backtrack_limit の制限に引っかかっているのでは？

[KazuhiroHatano]

コメントありがとうございます

PHP自体や実行環境の問題ってことなんでしょうか・・・

[melian]

コードに、

echo preg_last_error_msg();

を追加して実行してみたところ、

JIT stack limit exhausted

と表示されました。なので、preg_match の直前に以下を追加してみてください。

ini_set('pcre.jit', 0);

[KazuhiroHatano]

通りました、ありがとうございます。
正規表現の後戻り回数の問題なのですね。

AtCoderでini_setとかしていいのかも疑問だったのですが、まあ、通るならいいってことなんですよね

元々通ってたコードより、メモリ消費量は増えたものの実行時間は断然正規表現での方が短いようです。

後戻りが多そうな正規表現ではini_set('pcre.jit', 0);を入れてみるようにします。

[Zuishin]

解決したのであれば、他の人の役に立つよう自己解決してください。

Answer 1

いただいたコメントで解決したしました。
通らなかった原因はPHPの正規表現の処理の制限によるもので、正規表現のパターンでもini_set('pcre.jit', 0);を追加してJIT無効で実行することでACすることができました。

<?php
ini_set('pcre.jit', 0);
fscanf(STDIN,'%s',$s);
echo preg_match('/^(dream(er)?|eraser?)*$/',$s)?'YES':'NO';