algorithm - 寻找三个相等长度的子串

Question

给定一个字符串 S，我需要找到三个长度相等的子字符串。三个字符串中的每一个都不应重叠。此外，如果三个字符串是 A、B、C，则 S 可能不是 A+B+C。唯一要满足的条件是A要为前缀，B要在中间，C要为后缀。

每个字符串的最大长度是多少。

示例:让字符串 S="aaaaaa"那么这里的答案是 2。如何解决这个问题，请帮助。解释 :前缀边将为 aa{1, 2}。后缀边为 aa{6, 7}，Between 部分为 aa{3, 4} 或 aa{4, 5}。

这个问题是否有可能的 O(N) 解决方案？或者，如果不是，可以提出什么是最好的复杂度算法。

Answer 1

我认为这个问题可以通过前缀函数轻松解决。

考虑字符串 S[1 .. N] .首先，让我们计算一个前缀函数。在这一步之后，我们有一个数组 P[1 .. N] , 其中P[i]是子串S[1 .. i]的最大后缀的长度匹配它的前缀 P[i] < i .

然后我们只需要遍历整个字符串。对于每个 i , i = 2 .. N - 1我们假设中间的字符串结束于位置 i .

同时P[i]是S[1 .. i]的最长后缀匹配它的前缀和 P[N]是S[1 .. N]的最长后缀匹配它的前缀。

另请注意，我们的子字符串不能重叠。所以对于 S[1 .. i]匹配前缀且可以是所需子串的最长后缀的长度为min(P[i], i / 2) .对于 S[1 .. N]匹配前缀且可以是所需子串的最长后缀的长度受限于min(P[N], N - i) .

所以对于每个 i , i = 2 .. N - 1我们可以通过 min(min(P[i], i / 2), min(P[N], N - i)) 更新答案试图获得最大值。

此解决方案具有所需的线性复杂度。

例如，如果检查的字符串是 "aaaaaa" , 然后 P是[0, 1, 2, 3, 4, 5] .

之后我们尝试更新答案:

i = 2    min(min(1, 2 / 2), min(5, 6 - 2)) = 1
i = 3    min(min(2, 3 / 2), min(5, 6 - 3)) = 1
i = 4    min(min(3, 4 / 2), min(5, 6 - 4)) = 2
i = 5    min(min(4, 5 / 2), min(5, 6 - 5)) = 1

所以，答案是2 .