简单算法的辅助

Question

我目前正在从亚马逊买的一本书中学习算法，但这本书是世界上最糟糕的书，它展示了例子，但关键的是没有展示如何解决问题的答案。

所以我的第一个问题是，

Prefix-Match(T[1..n], P[1..m]) {
i := 1 // point to current position in T[]
while(i <= n) {
// find a match for first character of P
while( i <= n && T[i] != P[1]) i++
if (i > n) return; // quit
len := 1
// match as much as possible
while(len < m && i+len <= n && T[i+len] == P[1+len]) len++
output i, len
i++
}

如果T= a，b，a，b，c，a，b，p= a，b，a，？

其次，我如何计算算法的时间复杂度，以m和n表示？

Answer 1

那么，首先有一个问题:你说的是哪本书？如果这确实是它的代码样本，那么它一定很可怕……

现在来看答案：

• 这个函数遍历T的每个元素(这是第一个while循环)，
• 然后它在从"i“到表T的末尾的范围内找到P的第一个元素。在这种情况下，i = 1，因为T[1] == P[1] (如果T不包含P的第一个元素，则该函数简单地返回)，
• 然后查看从i开始的T中有多少元素与P中的后续元素匹配(这意味着它将获取元素T[i+1]并检查它是否与P[2]匹配，并与T[i+2]和P[3]相同)，然后
• 将打印它找到的i以及找到的匹配数。

基本上，此函数查找与P匹配的T的所有子集，确切的输出应如下所示：

1, 3
3, 2
6, 2

Tldr:第一个数字是元素P[1]在表T中所在的索引，第二个数字是紧跟在它后面的元素的数量等于它在表P中的对应物。

但我不知道作者的意图是什么--据我所知，找到的子集不必完全匹配P集，也就是说，如果我们取：T = [a,c,a]和P = [a,b,a]，我们仍然会得到输出1,3。如果在T中找到的子集的后续元素与其在P中的对应元素不同，则没有元素中断循环。

关于时间复杂性，网上有很多文章。如果你想要一本书，那么CLRS算法导论或算法设计手册是我的最爱。

Answer 2

这个程序的输出是T= a，b，a，b，c，a，b，P= a，b，a?？

要做到这一点，初学者的方法是拿出一支笔和一张纸，为每个变量留出一个槽。然后检查每条语句，就像计算机一样，并将写入的变量值作为语句执行的结果进行更改。

例如，如果您像上面那样从T和P开始，您将首先在i的插槽中通过i := 1 1设置T、n、P和m的值，然后您将通过while(i <= n) {，因为(1是< n)，依此类推...

当你这样做几次时，你将能够更快地完成它。

我目前正在从亚马逊买的一本书中学习算法，但这本书是世界上最糟糕的书，它展示了例子，但关键的是没有展示如何解决问题的答案。

所以我的第一个问题是，

 Prefix-Match(T[1..n], P[1..m]) {
  i := 1 // point to current position in T[]
  while(i <= n) {
     // find a match for first character of P
     while( i <= n && T[i] != P[1]) i++
     if (i > n) return; // quit
     len := 1
     // match as much as possible
     while(len < m && i+len <= n && T[i+len] == P[1+len]) len++
     output i, len
     i++
 }

这个程序的输出是T= a，b，a，b，c，a，b和P= a，b，a?？

，其次，我如何计算算法的时间复杂度，以m和n表示？

我不相信你已经准备好计算时间复杂度了，但想想m和n如何影响算法所需的最大时间(或者你需要多长时间才能手工完成)：

它依赖于m

• Does吗，它依赖于n

• If，它依赖于两者，它是m+n上的函数，还是更像m*n上的函数？也就是说，对于相同大小的T和两倍于P的大小，是否需要两倍的时间？