algorithm - isSubstring(s1, s2) 复杂性（语言无关方法）

Question

我刚读过一本概念性的书：

isString(sring s1, string s2)

可以假设为 O(A+B)，其中 A 是 s1 的大小，B 是 S2 的大小。

有人可以告诉这个假设来自哪里吗？

我的逻辑：如果我们假设 A > B 那么可以有 AB 窗口搜索。假设我们一找到它就退出。假设最坏的情况是序列中的最后一个字符每次都是假的。（不确定这样的序列是否存在）因此，我们在对单个窗口进行 B-1 比较后退出。综上所述，我们的总操作数应该是 AB*B-1。这是正确的逻辑还是我累了应该去睡觉）））））请告诉我。

标签： algorithmsubstring

Answer 1

对于一个固定的字符集，Ukkonen 的算法可以及时计算出Suffix Tree。验证是否是子字符串就是验证它是否是有效的后缀。遍历需要时间。从而导致时间。s1O(A)s2O(B)O(A + B)

正如您所描述的，天真的算法要慢得多。