在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： 算法的高层视图：

 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

- xcoder

---

我不理解这个问题。时间复杂度怎么可能取决于“String”的长度而不是元组列表的长度呢？ - Paul Boddington

@pbabcdefp 我已经编辑了问题并解释了为什么我认为它是O(n^2)。 - xcoder

重叠是什么意思？重叠是指元组相关还是S相关？您能给出更多的例子吗？ - coderz

@corderz中的overlap指的是如果S的两个子字符串共享至少1个位置。 (3,3)与(4,2)重叠，因为它们共享“de”（S [4]和S [5]，S从1开始）。 - xcoder

另外，如果(0, 2)与(1, 2)发生碰撞，您需要报告两个元组还是其中一个？ - user2357112

Answer 1

你的基本思路是正确的，但你可以优化停止条件，以保证最坏情况下复杂度有界。想一想 - 在最坏情况下，你需要遍历和标记 S 中多少个位置？

如果没有碰撞，那么最坏情况下你会访问 length(S) 个位置（并在此之前用完元组，因为任何额外的元组都必须发生碰撞）。如果出现碰撞 - 你可以在第一个标记的对象处停止，因此你的上限是未标记元素的最大数量，即 length(S)。

编辑：由于你添加了一个要求来报告所有碰撞元组，让我们再次计算一下（扩展我的评论） -

一旦你标记了所有元素，你可以通过单步操作（O(1)）检测每一个进一步的元组是否发生碰撞，因此你需要 O(n+n) = O(n)。这一次，每一步都将标记一个未标记元素（最坏情况下总共 n 个），或者识别一个碰撞的元组（最坏情况下也是 n）。

实际步骤可能是交错的，因为元组可以以任何方式组织而不会首先发生冲突，但一旦它们这样做（在最多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）]

- Leeor

---

谢谢你的回答。关于你的第一个问题，应该是S的长度吧？例如，第一个元组覆盖整个S，那么接下来的所有元组都会发生碰撞。因此，第一个外部循环运行n次，然后接下来的循环每次只运行O(1)次......这样正确吗？ - xcoder

@xcoder，如果外层循环迭代元组，则它将运行一次（在第一个元组上），内层循环将标记所有n个元素为已触摸，然后在第二个元组的第一次检查时立即退出，因为它会发生碰撞。 - Leeor

也许我应该更清楚地表达。一旦检测到碰撞，我就无法退出。想象一下，我需要报告所有后续发生碰撞的元组，因此我必须遍历整个元组列表。 - xcoder

这是添加新约束条件，但不会增加复杂度。一旦标记了所有元素，您可以使用单个检查（O（1））检测每个进一步的元组碰撞，因此您需要O（n + n）= O（n）-每个检查都将标记未标记的元素（最坏情况下总共n），或识别出冲突的元组（最坏情况下为O（元组），我们假设也是n）。 - Leeor

哦！现在开始有意义了！这不是O(n^2)，因为对于检查，我不需要每次遍历整个列表！我只是想知道，如果元组列表像[(n,1),(n-1,1),...(1,1)]，会改变什么吗？ - xcoder

@xcoder - 这是很好的一点 - 没有关系。每个步骤都将标记一个元素（一次并且永久），或检测到碰撞并继续到下一个元组。在这个最后的例子中，您只需要进行O(n)标记步骤，并查看是否没有冲突。一个更有趣的例子（也许这就是你的意思？）是如果该列表是：[(1，n)，（n，1），（n-1，1），...（1，1）] - 第一个元素将遍历整个数组一次，其余元素将每个取1步。 - Leeor

Answer 2

根据您的描述和评论，重叠问题可能与字符串算法无关，可以视为“段重叠”问题。

以您的示例为例，它可以被分解为3个段：[1,2]、[3,5]、[4,5]。问题是检查这3个段是否有重叠。

假设我们有m个段，每个段都有格式[start, end]，表示段开始位置和结束位置，一种有效的检测重叠的算法是按照起始位置升序排序它们，这需要O(m * lgm)时间。然后迭代排序后的m个段，对于每个段，尝试找到其结束位置，这里只需要检查：

if(start[i] <= max(end[j], 1 <= j <= i-1) {
    segment i is overlap;
}
maxEnd[i] = max(maxEnd[i-1], end[i]); // update max end position of 1 to i

每次检查操作都需要O(1)的时间。那么总时间复杂度为O(m*lgm + m)，可以视为O(m*lgm)。而对于每个输出，时间复杂度与每个元组的长度有关，这也与n有关。

- coderz

Answer 3

这是一个段重叠问题，如果元组列表按照第一个字段的升序排序，则解决方案应该在O(n)内完成。考虑以下方法：

1. 将区间从（开始，字符数）转换为（开始，包含结束）。因此，上面的示例变为：[(1,2),(3,3),(4,2)] ==> [(1, 2), (3, 5), (4, 5)]

2. 如果转换后的连续元组(a,b)和(c,d)总是遵循b < c，则元组有效。否则，上述元组中存在重叠。

如果按照上述形式对数组进行排序，则可以在O(n)内完成1和2中的每个操作。

- user1952500