How to find unique strings in php

PHP is a very popular web programming language that is widely used to develop dynamic websites and web applications. During the development process, it is often necessary to process strings, such as finding unique strings. This article will introduce how to use PHP to write a powerful program to find unique strings.

1. What is a non-repeating string

In computer science, a non-repeating string refers to a substring without repeated characters in a string. For example, in the string "hello world", the non-repeating substrings are "hel", "helo", "hell", "hello", "wor", "world", etc.

2. Algorithm for finding unique strings

To find unique strings, we need to use an algorithm to process strings. Commonly used algorithms include "sliding window" and "hash table".

1. Sliding window algorithm

The sliding window algorithm is a very effective string processing algorithm that can find unique strings in O(n) time complexity String.

The steps of this algorithm are as follows:

1) Define two pointers left and right, which point to the first character of the string respectively.

2) Use a hash table to record the number of occurrences of each character.

3) Move the right pointer to the right until repeated characters are encountered.

4) Move the left pointer to the right until there are no more repeated characters.

5) Repeat steps 3 and 4 until the right pointer reaches the end of the string.

6) Calculate the length of each non-repeating substring and find the longest non-repeating substring.

The following is the PHP implementation of this algorithm:

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. Hash table algorithm

The hash table algorithm is a data structure used for fast lookup. It can quickly find whether an element exists in the hash table. The implementation idea of ​​this algorithm is:

1) Use a hash table to store the position where characters appear.

2) Traverse the string, if the character is not in the hash table, add it to the hash table, otherwise update the position information of the character.

3) Record the starting and ending positions of non-repeating substrings.

4) Update the length of the longest substring.

5) Return the length of the longest substring.

The following is the PHP implementation of this algorithm:

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. Test program

In order to verify the correctness of the above algorithm, we wrote a test program. This program can randomly generate a string and use the above two algorithms to find the longest non-repeating substring. We can execute the program in a loop to verify the accuracy and execution time of the algorithm.

The following is the PHP code of the test program:

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. Summary

This article introduces how to use PHP to write a Program to find non-repeating substrings, and introduces two commonly used algorithms: sliding window algorithm and hash table algorithm. The sliding window algorithm is an efficient algorithm with a time complexity of O(n) and is suitable for processing large-scale data; the hash table algorithm is more controllable in terms of space utilization, but its time complexity is high. The test procedures in the program can help us verify the execution time and correctness of the algorithm, so as to select the algorithm that is most suitable for the current scenario.

The above is the detailed content of How to find unique strings in php. For more information, please follow other related articles on the PHP Chinese website!