估计我的代码大O，朴素模式匹配

Question

>我正在尝试解决 CLRS 书中的练习 32.1-2，这是关于字符串算法、朴素模式搜索的

假设模式 P 中的所有字符都不同。展示如何加速 朴素字符串匹配器在时间 O(n( 中对 n 个字符的文本运行。

所以我正在尝试优化我想出的天真的蛮力解决方案，但我认为我不能做得更好，将整体运行时间减少到 O(n(。

<?php
//naive search
$a = array('a', 'b', 'u', 'c');
$b = array('a','b','u','c','a','b','u','c','b','a','b','u','c','b', 'a', 'b','c');
//index     0   1  2    3  4   5    6   7  8    9  10   11 12  13  14    15   16
$n = count($b);
$k = count($a);
$counter = 0;
for($i=0;$i<$n - $k ;$i++){   // big- O (n)

//since its "exact string matching problem" i am testing here so i don't dive into second loop unless the ith character of B is matching the first char of the pattern 
if($b[$i] == $a[0]){
for($j=$i; $j<$k; $j++){ // big O(k)
if($b[$j] == $a[$j])
$bool = true;
else {
$bool = false;
break;   
}
}
if($bool){
echo "Found at index: ".$i."<br>";
$counter++;
}
// since pattern match cant overlap with another one, so when one is found jump by K iteration, here is all what I could do about the pattern's value being distinct, is there any possible optimization I can do
$i = $i + $k - 1;   
}

}
echo $counter;
?> 

我当然减少了这个特定实例的运行时间，但想象一下最坏的情况是所有字符都设置为"a"的文本，我将每次进入第二个循环，即 O(k*n(。

算法的大O是什么？ 我能得到更有效的解决方案吗？

Answer 1

你也得到了正确的想法("因为模式匹配不能与另一个重叠"(。 像这样的东西应该适用于主循环：

for($i=0;$i<$n - $k ;$i++){
for($j=0; $j<$k; $j++){
$last_matched = $j + $i;
if($b[$j + $i] == $a[$j])
$bool = true;
else {
$bool = false;
break;   
}
}
if($bool){
echo "Found at index: ".$i."<br>";
$counter++;
}
// this line is important
$i = $last_matched + 1;   
}

请注意重要的行。 在这里，我们告诉算法在上一次匹配失败(或完成(后开始下一次匹配尝试。 这是因为模式具有不同的字符，并且如果您已经匹配了j个字符，然后匹配了j+1字符失败，则真正的匹配将重叠该区域(如果它们重叠，则模式中的某些字符应该是相同的，这是矛盾的(。

现在，更改后的算法的复杂性将为 O(n(。这是因为内部循环中的 if 条件只会对文本的每个字符执行一次(请记住，在内部循环完成或中断后，我们在其最后一个位置之后开始外部循环(。

PS：乘以循环复杂性通常是正确的，但你并不总是得到尽可能严格的界限。