首頁 後端開發 PHP問題 php怎麼查找不重複字串

php怎麼查找不重複字串

Mar 29, 2023 am 10:11 AM

PHP是一種非常流行的Web程式語言,它廣泛用於開發動態網站和Web應用程式。在開發過程中,經常需要對字串進行處理,例如尋找不重複的字串。本文將介紹如何用PHP寫一個強大的尋找不重複字串的程式。

一、什麼是不重複字串

在電腦科學中,不重複字串指的是一個字串中沒有重複字元的子字串。例如,在字串"hello world"中,不重複子字串為"hel", "helo", "hell", "hello", "wor", "world"等。

二、尋找不重複字串的演算法

要尋找不重複字串,我們需要使用一種演算法來處理字串。常用的演算法有“滑動視窗”和“哈希表”。

  1. 滑動視窗演算法

滑動視窗演算法是一種非常有效的字串處理演算法,它可以在O(n)的時間複雜度內尋找不重複字串。

此演算法的步驟如下:

1)定義兩個指標left和right,分別指向字串的第一個字元。

2)使用雜湊表來記錄每個字元出現的次數。

3)將right指標向右移動,直到遇到重複字元。

4)將left指標向右移動,直到不再有重複字元。

5)重複步驟3和4,直到right指標到達字串的末端。

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;
登入後複製

}

  1. 雜湊表演算法

哈希表演算法是一種用於快速尋找的資料結構,它可以快速找到某個元素是否存在於雜湊表中。此演算法的實作想法是:

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;
登入後複製

}

三、測試程式

為了驗證以上演算法的正確性,我們寫了一個測試程式。該程式可以隨機產生一個字串,並使用以上兩種演算法來尋找最長的不重複子字串。我們可以透過循環執行該程序,驗證演算法的準確性和執行時間。

下面是測試程式的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);
登入後複製

}

四、總結

##本文介紹如何用PHP寫一個尋找不重複子字串的程序,並介紹了兩種常用演算法:滑動視窗演算法和哈希表演算法。滑動視窗演算法是一種高效率的演算法,其時間複雜度為O(n),適用於大規模資料的處理;雜湊表演算法則在空間利用上較為可控,但其時間複雜度較高。程式中的測試程序可以幫助我們驗證演算法的執行時間和正確性,從而選出最適合當前場景的演算法。

以上是php怎麼查找不重複字串的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1666
14
CakePHP 教程
1425
52
Laravel 教程
1328
25
PHP教程
1273
29
C# 教程
1253
24