1

私は (楽しみのために) 回文を認識するスクリプトの作成に取り組んでいました。これまでのところ、「カヤック」、「レースカー」、「アンナ」、「パナマ運河を計画する男」などで成功しています。

余談ですが、PCRE を使用すると物事がはるかに簡単になることは理解していますが、私は PCRE に精通していません。私の主な目的の 1 つは、回文のチェックの背後にあるアルゴリズムを理解することでした。

 <?php
$word = "amanaplana canalpan ama";

$space = " ";
$word_smallcase = strtolower($word);        

$word_array = str_split($word_smallcase);   

if(in_array($space, $word_array)){      

    for($m = 0; $m<count($word_array); $m = $m + 1){
        if($word_array[$m] == $space)
            unset($word_array[$m]);
    }
}
$count = 0;
$scan_count = -1;
for($i = 0; $i < (count($word_array)/2); $i = $i + 1){

    for($j = count($word_array); $j > (count($word_array)/2); $j = $j - 1){

        if($word_array[$i]==$word_array[$j]){
            $count = $count + 1;
            break;
            }
        }
    $scan_count = $scan_count + 1;

        }
if ($count == $scan_count){
    echo $word." is a palindrome";
}
else{

    echo $word ." is NOT a palindrome";
}


?>

次の点についてご回答いただければ幸いです。

  • 私が抱えているバグの識別。
  • コードをどのように改善できるかについての推奨事項 (私の目には比較的素人っぽく見える $count や $scan_count に頼らずに物事を機能させることができれば幸いです)。

前もって感謝します。

4

5 に答える 5

2

ここでいくつかのことが起こっています...

unsetまず、配列を 'ingしても実際にはインデックスが削除されないことに気付いているかどうかはわかりません。

$array = array(0, 1, 2, 3);
unset($array[2]);
var_dump($array);
/* array(3) {
  [0]=>
  int(0)
  [1]=>
  int(1)
  [3]=>
  int(3)
} */

したがって、配列内の要素を反復処理すると、未定義のオフセットがいくつか発生します。1 つずつ移動するには、foreachループ コントロールを使用する必要があります。

もう 1 つの問題は、ネストされた for ループにあります。

for($i = 0; $i < (count($word_array)/2); $i = $i + 1){

    for($j = count($word_array); $j > (count($word_array)/2); $j = $j - 1){

「amanaplanacanalpanama」が与えられた場合、何をしているのか見てみましょう:

段階的に比較します (ところで、$j の初期化子で 1 ずれています... $word_array[count($word_array)]'a' ではなく、パナマの 'm' を指しています。):

a eq to a?              j is 22          i is 0
                scan_count: -1   count: 1
m eq to a?              j is 22          i is 1
m eq to m?              j is 21          i is 1
                scan_count: 0    count: 2
a eq to a?              j is 22          i is 2
                scan_count: 1    count: 3

a eq to am は次の反復で見つかりますが、次の「a」に到達すると、パナマの最後にある元の「a」が見つかります...

補足として、毎回最後からやり直すのでO(n^2)、十分に大きな文字列を考えると、恐ろしく非効率的です...

必須の解決策:

$word = "amanaplana canalpan ama";

$j = strlen ($word)-1;
$pal = true;

for ($i = 0; $i < strlen($word)/2; ++$i, --$j) {

    // skip spaces
    while ($word[$i] === " ") {$i++;}
    while ($word[$j] === " ") {$j--;}

    echo "$word[$i] eq $word[$j]?\n";
    if ($word[$i] !== $word[$j])    {
        $pal = false;
        break;
        }
}

if ($pal) print "yes"; else print "no";
于 2011-07-17T13:00:04.510 に答える
1

疑似コード:

string phrase = "my phrase here"

int i = 0
int j = phrase.length - 1

while i < j:
  if phrase[i] is not alphanumeric:
    i++;
    continue;
  if phrase[j] is not alphanumeric:
    j--;
    continue;
  if phrase[i] != phrase[j]
    return false;
  i++;
  j--;

return true
于 2011-07-17T06:35:53.793 に答える
0

すべてのスペースを削除して、単語を完全に無視することは可能だと思います。2つに分割し（文字列の長さが奇数の場合はそのあたり）、半分を逆にして、それらが一致するかどうかを確認します。

$word = "amanaplana canalpan ama";

$sanitizedWord = preg_replace("'\s+'", '', strtolower($word));
$halfway = strlen($sanitizedWord)/2;
$roundedDownMidPoint = floor($halfway);

$firstHalf = substr($sanitizedWord, 0, $roundedDownMidPoint);
$secondHalf = substr($sanitizedWord, is_float($halfway) ? $roundedDownMidPoint+1 : $halfway);

if ($firstHalf === strrev($secondHalf)) {
    echo $sanitizedWord." is a palindrome";
}

「カヤック」、「レースカー」、「アンナ」、「男はパナマ運河を計画している」、「アマナプラナ運河アマ」はすべて回文として正しく識別されています。

于 2011-07-17T06:51:20.363 に答える
0 
<?php
$a="amanaplana canalpan ama";
echo "String entered: " . $a;
$b= preg_replace('/\s+/', '', $a);
$org= strtolower($b);
$chk= strrev($org);
echo "<br/>";
if ($org==$chk)
{ echo "Palindrome"; }
else
{ echo "Not Palindrome"; }
?>
于 2014-03-17T08:19:20.627 に答える