子串查找

介绍

子串查找，也可以成为字符串查找。其中有两个字符串，分为主串和子串(模式串)。在主串中查找是否含有子串，且顺序长度相等。

创建 strstr.php 内容如下：

<?php 
function main($mainString,$subString){
	$result = false;
	$mainStringLen = strlen($mainString);
	$subStringLen = strlen($subString);
	for ($i=0; $i < $mainStringLen-$subStringLen+1; $i++) { 
		if ($mainString[$i]==$subString[0]) {
			$end = 0;
			for ($j=0; $j < $subStringLen; $j++) { 
				$end = $j;
				if ($mainString[$i+$j]!=$subString[$j]) {
					break;
				}
			}
			if ($end==$subStringLen-1) {
				$result = true;
			}
		}
	}
	return $result;
}
var_dump(main("mongodb","go"));

执行

1 2	$ php strstr.php bool(true)

最大公共子串

介绍

最大公共子串，即存在两个字符串中，交集长度最多的一串字符，且顺序长度相等。

创建 maxSubStr.php 内容如下：

<?php 
function main($str1,$str2){
	$maxSubstr = "";
	$maxLen = $m = $n = $str1len = $str2len = 0;
	for ($i = 0; $i < strlen($str1); $i++) { 
		for ($j = 0; $j < strlen($str2); $j++) { 
			if ($str1[$i] == $str2[$j]) {
				$str1len = strlen($str1);
				$str2len = strlen($str2);
				for ($m = $i,$n = $j; $m<$str1len,$n<$str2len ; $m+=1,$n+=1) { 
					if ($str1[$m]!=$str2[$n]) {
						break;
					}
					if ($maxLen<$m-$i) {
						$maxLen = $m-$i;
						$maxSubstr = substr($str1, $i, $m+1+$i);
					}
				}
			}
		}
	}
	return $maxSubstr;
}
var_dump(main("ElasticSearch","ElasticHD"));

上述代码用了三层 for 循环，因此时间复杂度为 O(n)^3。

使用动态规划方法优化如下。

<?php 
function main($str1,$str2){
	$str1len = strlen($str1);
	$str2len = strlen($str2);
	$m = array_fill(0, $str2len, array_fill(0, $str1len, 0));
	for ($i = 0; $i < $str2len; $i++) { 
		for ($j = 0; $j < $str1len; $j++) { 
			if ($str2[$i-1] == $str1[$j-1]) {
				$m[$i][$j] = $m[$i-1][$j-1]+1;
			}
		}
	}
	$max = $index = 0;
	for ($x = 0; $x < $str2len; $x++) { 
		for ($y = 0; $y < $str1len; $y++) { 
			if ($m[$x][$y]>$max) {
				$max = $x;
				$index = $x;
			}
		}
	}
	$maxSubstr = "";
	for ($i = $index-$max; $i < $index; $i++) { 
		$maxSubstr.=$str2[$i];
	}
	return $maxSubstr;
}
var_dump(main("ElasticSearch","ElasticHD"));

执行

1 2	$ php maxSubStr.php Elastic

翻转单词

介绍

翻转单词，把一段英文单词构成的字符串的顺序逆转。

创建 reverseWord.php 内容如下：

<?php 
# 方案一
function main($str){
	$arr = explode(" ", $str);
	$reverseArr = [];
	for ($m = count($arr)-1,$n=0; $m >= 0; $m-=1,$n+=1) { 
		$reverseArr[$n] = $arr[$m];
	}
	return implode($reverseArr, " ");
}
var_dump(main("she and he"));

# 方案二
function main2($str){
	$arr = explode(" ", $str);
	$m = count($arr);
	for ($i=0; $i < $m/2; $i++) { 
		$temp = $arr[$i];
		$arr[$i] = $arr[$m-$i-1];
		$arr[$m-$i-1] = $temp;
	}
	return implode($arr, " ");
}
var_dump(main2("she and he"));

执行

1 2	$ php reverseWord.php he and she