arrays - 在 O(n) 时间内检查两个子串是否重叠

Question

如果我有一个长度为n的字符串S，和一个元组列表(a,b)，其中a指定了S的子串的起始位置，b是子串的长度。要检查是否有任何子串重叠，我们可以，例如，标记 S 中的位置，只要它被触摸。但是，我认为如果元组列表的大小为 n(循环元组列表，然后循环 S)，这将花费 O(n^2) 时间。

是否有可能在 O(n) 时间内检查任何子串是否与另一个子串实际重叠？

编辑: 例如，S = "abcde"。元组 = [(1,2),(3,3),(4,2)]，代表“ab”、“cde”和“de”。我想知道在读取 (4,2) 时发现重叠。

我认为它是 O(n^2) 因为你每次都得到一个元组，然后你需要遍历 S 中的子字符串以查看是否有任何字符被标记为脏。

编辑 2: 一旦检测到碰撞，我就无法退出。想象一下，我需要报告所有发生冲突的后续元组，因此我必须遍历整个元组列表。

编辑 3: 算法的高级 View :

 for each tuple (a,b)
   for (int i=a; i <= a+b; i++)
      if S[i] is dirty 
        then report tuple and break //break inner loop only

Answer 1

您的基本方法是正确的，但您可以优化停止条件，以保证在最坏情况下的有限复杂性。这样想——在最坏的情况下，你需要遍历和标记 S 中的多少个位置？

如果没有碰撞，那么在最坏的情况下，您将访问 length(S) 个位置(到那时用完元组，因为任何额外的元组都必须碰撞)。如果发生碰撞 - 你可以在第一个标记的对象处停止，所以你再次受到未标记元素的最大数量的限制，即长度(S)

编辑:由于您添加了报告所有 碰撞元组的要求，让我们再次计算(扩展我的评论)-

一旦您标记了所有元素，您就可以通过单个步骤 (O(1)) 检测每个其他元组的碰撞，因此您需要 O(n+n) = O(n)。 这一次，每个步骤要么标记一个未标记的元素(在最坏的情况下总的 n)，要么识别一个冲突的元组(我们假设也是 n 的最坏的 O(tuples))。

实际的步骤可能是交错的，因为元组可以以任何方式组织而不会首先发生碰撞，但是一旦它们发生碰撞(在第一次碰撞之前最多覆盖所有 n 个元素的 n 个元组之后)，你必须碰撞每次都在第一步。甚至在标记所有元素之前，其他安排可能会更早发生冲突，但同样 - 您只是重新安排相同数量的步骤。

最坏的例子:一个元组覆盖整个数组，然后是 n-1 个元组(哪个无关紧要)- [(1,n), (n,1), (n-1,1), ...(1,1)]

第一个元组需要 n 个步骤来标记所有元素，其余每个需要 O(1) 来完成。总体 O(2n)=O(n)。现在说服自己以下示例采用相同数量的步骤 -

[(1,n/2-1), (1,1), (2,1), (3,1), (n/2,n/2), (4,1), (5 ,1) ...(n,1)]