PHPで一意の文字列を見つける方法

PHP は、動的な Web サイトや Web アプリケーションの開発に広く使用されている、非常に人気のある Web プログラミング言語です。開発プロセスでは、一意の文字列を検索するなど、文字列を処理することが必要になることがよくあります。この記事では、PHP を使用して一意の文字列を検索する強力なプログラムを作成する方法を紹介します。

1. 非繰り返し文字列とは

コンピューター サイエンスでは、非繰り返し文字列とは、文字列内に繰り返し文字がない部分文字列を指します。たとえば、文字列「hello world」の場合、繰り返されない部分文字列は「hel」、「helo」、「hell」、「hello」、「wor」、「world」などです。

2. 一意の文字列を見つけるためのアルゴリズム

一意の文字列を見つけるには、文字列を処理するアルゴリズムを使用する必要があります。一般的に使用されるアルゴリズムには、「スライディング ウィンドウ」や「ハッシュ テーブル」などがあります。

1. スライディング ウィンドウ アルゴリズム

スライディング ウィンドウ アルゴリズムは、O(n) 時間計算量の文字列内で一意の文字列を見つけることができる、非常に効果的な文字列処理アルゴリズムです。

このアルゴリズムの手順は次のとおりです。

1) 文字列の最初の文字をそれぞれ指す、左右の 2 つのポインターを定義します。

2) ハッシュ テーブルを使用して、各文字の出現数を記録します。

3) 繰り返される文字が見つかるまで、右ポインタを右に移動します。

4) 繰り返される文字がなくなるまで、左ポインタを右に移動します。

5) 右ポインタが文字列の末尾に到達するまで、手順 3 と 4 を繰り返します。

6) それぞれの非繰り返し部分文字列の長さを計算し、最長の非繰り返し部分文字列を見つけます。

次は、このアルゴリズムの PHP 実装です:

function findLongestSubstring($str){

$n = strlen($str);
$set = array();
$ans = $i = $j = 0;
while ($i < $n && $j < $n) {
    if (!isset($set[$str[$j]])) {
        $set[$str[$j++]] = true;
        $ans = max($ans, $j - $i);
    } else {
        unset($set[$str[$i++]]);
    }
}
return $ans;

}

2. ハッシュ テーブル アルゴリズム

ハッシュ テーブル アルゴリズムは、高速検索に使用されるデータ構造であり、ハッシュ テーブルに要素が存在するかどうかを迅速に見つけることができます。このアルゴリズムの実装アイデアは次のとおりです。

1) ハッシュ テーブルを使用して、文字が出現する位置を保存します。

2) 文字列を走査し、文字がハッシュ テーブルにない場合はハッシュ テーブルに追加し、そうでない場合は文字の位置情報を更新します。

3) 非反復部分文字列の開始位置と終了位置を記録します。

4) 最長の部分文字列の長さを更新します。

5) 最長の部分文字列の長さを返します。

次は、このアルゴリズムの PHP 実装です:

function findLongestSubstring($str){

$n = strlen($str);
$map = array();
for ($i = $j = $ans = 0; $j < $n; $j++) {
    if (isset($map[$str[$j]])) {
        $i = max($map[$str[$j]], $i);
    }
    $ans = max($ans, $j - $i + 1);
    $map[$str[$j]] = $j + 1;
}
return $ans;

}

3. テスト プログラム

上記のアルゴリズムが正しいことを検証するために、テスト プログラムを作成しました。このプログラムは文字列をランダムに生成し、上記の 2 つのアルゴリズムを使用して最長の非反復部分文字列を見つけることができます。プログラムをループで実行して、アルゴリズムの精度と実行時間を検証できます。

以下はテスト プログラムの PHP コードです:

function randomString($length = 10) {

$str = '';
$chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
for ($i = 0; $i < $length; $i++) {
    $str .= $chars[rand(0, strlen($chars) - 1)];
}
return $str;

}

$N = 5 ;
for ($i = 0; $i < $N; $i ) {

$str = randomString(100000);
$start = microtime();
$ans1 = findLongestSubstring($str);
$end = microtime();
$time1 = ($end - $start) * 1000;

$start = microtime();
$ans2 = findLongestSubstring($str);
$end = microtime();
$time2 = ($end - $start) * 1000;

printf("Test case %d: %s\n", $i + 1, $str);
printf("滑动窗口算法: %d (%.3fms)\n", $ans1, $time1);
printf("哈希表算法: %d (%.3fms)\n", $ans2, $time2);

}

4. 概要

この記事では、次の方法を紹介します。 PHP を使用して非反復部分文字列を見つけるプログラムを作成し、スライディング ウィンドウ アルゴリズムとハッシュ テーブル アルゴリズムという 2 つの一般的に使用されるアルゴリズムを導入します。スライディング ウィンドウ アルゴリズムは、時間計算量が O(n) の効率的なアルゴリズムであり、大規模なデータの処理に適しています。ハッシュ テーブル アルゴリズムは、スペース利用の点で制御しやすいですが、時間計算量は高くなります。プログラム内のテスト手順は、現在のシナリオに最適なアルゴリズムを選択するために、アルゴリズムの実行時間と正確さを検証するのに役立ちます。

以上がPHPで一意の文字列を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。