0

假设给我一个字符串 S。

我需要找到包含 S1 作为前缀和 S2 作为后缀的 S 的不同子字符串的数量。

S、S1、S2的范围可以很大，即O(10^5)。

例如。

假设 S 是“abcdcd”，S1 是“ab”，S2 是“cd”。

“ababcdcd”的不同子串是：“a”、“b”、“c”、“d”、“ab”、“bc”、“cd”、“dc”、“abc”、“bcd”、“ cdc”、“dcd”、“abcd”、“bcdc”、“cdcd”、“abcdc”、“bcdcd”、“abcdcd”。使用 Suffix Array 可以轻松找到不同子串的总数。我正在尝试扩展相同的想法来解决问题。

在这些子串中，包含“ab”作为前缀和“cd”作为后缀的子串是：“abcd”、“abcdcd”。

因此答案是2。

PS：我相信它使用后缀数组，但我不确定如何。请帮忙。

4

1 回答 1

0

解决方案很简单：

  • 构建所有前缀出现的列表。
  • 建立一个所有出现的后缀的列表。
  • 计算有效组合。

复杂度：O(#S+#S1)+O(#S+#S2)+O(#found(S1)+#found(S2))

可选而不是省略这些数组：

startpos, endpos, startcount, ret = -1, -1, 0, 0
while startpos = find new embedding of S1 after startpos
  while (endpos-startpos)<max(#S1,#S2)
    if not endpos = find new embedding of S2 after endpos
      return ret
    ret = ret + startcount
  startcount = startcount + 1
return ret

复杂度现在应该是 O(2*#S+#S1+#S2)。但我不确定...

于 2014-03-30T00:27:19.077 回答