Bagaimana untuk mencari rentetan unik dalam php

PHP ialah bahasa pengaturcaraan web yang sangat popular, yang digunakan secara meluas untuk membangunkan tapak web dinamik dan aplikasi web. Semasa proses pembangunan, selalunya perlu memproses rentetan, seperti mencari rentetan unik. Artikel ini akan memperkenalkan cara menggunakan PHP untuk menulis program yang berkuasa untuk mencari rentetan unik.

1. Apakah rentetan unik

Dalam sains komputer, rentetan unik merujuk kepada subrentetan tanpa aksara berulang dalam rentetan. Contohnya, dalam rentetan "hello world", subrentetan tidak berulang ialah "hel", "helo", "hell", "hello", "wor", "world", dsb.

2. Algoritma untuk mencari rentetan unik

Untuk mencari rentetan unik, kita perlu menggunakan algoritma untuk memproses rentetan. Algoritma yang biasa digunakan termasuk "tetingkap gelongsor" dan "jadual cincang".

1. Algoritma Tetingkap Gelongsor

Algoritma Tetingkap Gelongsor ialah algoritma pemprosesan rentetan yang sangat berkesan yang boleh mencari rentetan unik dalam Rentetan kerumitan masa O(n).

Langkah-langkah algoritma ini adalah seperti berikut:

1) Tentukan dua penunjuk kiri dan kanan, yang masing-masing menghala ke aksara pertama rentetan.

2) Gunakan jadual cincang untuk merekodkan bilangan kejadian bagi setiap aksara.

3) Gerakkan penuding kanan ke kanan sehingga ia menemui aksara berulang.

4) Gerakkan penuding kiri ke kanan sehingga tiada lagi aksara berulang.

5) Ulang langkah 3 dan 4 sehingga penunjuk kanan sampai ke hujung rentetan.

6) Kira panjang setiap subrentetan tidak berulang dan cari subrentetan tidak berulang terpanjang.

Berikut ialah pelaksanaan PHP bagi algoritma ini:

fungsi 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. Jadual cincang algoritma

Algoritma jadual cincang ialah struktur data yang digunakan untuk carian pantas Ia boleh mencari dengan cepat sama ada unsur wujud dalam jadual cincang. Idea pelaksanaan algoritma ini ialah:

1) Gunakan jadual cincang untuk menyimpan kedudukan di mana aksara muncul.

2) Lintas rentetan, jika aksara tiada dalam jadual cincang, tambahkannya pada jadual cincang, jika tidak kemas kini maklumat kedudukan watak itu.

3) Rakam kedudukan permulaan dan penamat subrentetan tidak berulang.

4) Kemas kini panjang subrentetan terpanjang.

5) Kembalikan panjang subrentetan terpanjang.

Berikut ialah pelaksanaan PHP bagi algoritma ini:

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 🎜>

Untuk mengesahkan ketepatan algoritma di atas, kami menulis program ujian. Atur cara ini boleh menjana rentetan secara rawak dan menggunakan dua algoritma di atas untuk mencari subrentetan tidak berulang terpanjang. Kita boleh melaksanakan program dalam gelung untuk mengesahkan ketepatan dan masa pelaksanaan algoritma.

Berikut ialah kod PHP program ujian:

function randomString($length = 10) {

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

}

$N = 5;

untuk ($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 artikel memperkenalkan cara Gunakan PHP untuk menulis program untuk mencari subrentetan unik, dan memperkenalkan dua algoritma yang biasa digunakan: algoritma tetingkap gelongsor dan algoritma jadual cincang. Algoritma tetingkap gelongsor ialah algoritma yang cekap dengan kerumitan masa O(n) dan sesuai untuk memproses data berskala besar algoritma jadual cincang lebih terkawal dari segi penggunaan ruang, tetapi kerumitan masanya adalah tinggi. Prosedur ujian dalam program boleh membantu kami mengesahkan masa pelaksanaan dan ketepatan algoritma, untuk memilih algoritma yang paling sesuai untuk senario semasa.

Atas ialah kandungan terperinci Bagaimana untuk mencari rentetan unik dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!