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

Question

我刚刚在一本概念性的书中读到:

isString(sring s1, string s2)

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

谁能告诉我这个假设是从哪里来的？

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

Answer 1

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

正如您所描述的，朴素算法要慢得多。