2

我正在寻找一种算法来找到给定字符串的主要循环子字符串。

循环子串：

  • 相邻重复两次或更多次的子串。

一个占主导地位的循环子串：

  • 具有最相邻重复的子串占主导地位
  • （相邻重复出现的次数相同）
    • 最长的子串占主导地位
  • （关于长度和相邻重复的关系）
    • 首先出现的子串占主导地位

示例 1：

  • prefixgarbagecyclecyclecyclecyclesufixgarbage
  • 返回cycle:=>cycle是重复次数最多的相邻子字符串

示例 2：

  • prefixgarbagecyclepadinggarbagecyclesufixgarbage
  • 返回g:=> 的出现cycle不相邻g重复，相邻重复两次

示例 3：

  • prefixgarbagecyclecyclepadinggarbageprefixgarbage
  • 返回cycle:=> cycle&g相邻重复两次但cycle更长g

示例 4：

  • prefixgarbagecyclecyclecycleroundroundroundprefixgarbage
  • 返回cycle:=> cycle&round相邻重复三次 & 相同长度但cycle首先出现

例 5：

  • abcdefghijklmnopqrstuvqxyz
  • 返回<empty string>，因为没有重复的相邻子字符串

实现此算法的最佳方法是什么？

4

4 回答 4

2

找不到比这个二次时间算法更好的东西（用 Python 实现）：

IREP, IPER, IPOS = 0, 1, 2

def find_dominant(src):
  best = (0, 0, 0) # repetitions-1, period, position

  period = 0
  while period < len(src) // max(2, 1 + best[IREP]):
    period += 1
    length = 0

    for pos in range(len(src) - 1 - period, -1, -1):
      if src[pos] == src[pos + period]:
        length += 1
        repetitions = length // period
        if repetitions >= best[IREP]:
          best = (repetitions, period, pos)
      else:
        length = 0

  return best


s = "prefixgarbagecyclecyclecyclecyclesufixgarbage"
res = find_dominant(s)
if res[0] == 0:
  print("nothing found")
else:
  print(res[IREP] + 1, '*', s[res[IPOS]: res[IPOS] + res[IPER]])

对于每个可能的周期，扫描字符串并记住最长的周期子序列。向后扫描以检查较少的条件。在没有进一步改善的情况下停止增加周期。

时间复杂度为 O(N 2 / R)，其中 R 是主导子串的重复次数。空间复杂度为 O(1)。

于 2013-09-13T19:18:03.530 回答
1

这是一种可能的方法（由于您的周期必须相邻，因此变得更简单）。选择一个字符串。看看会不会重复。跟踪最重复的一个。

编辑实际测试过的 Python 代码：

testStrings =[ "prefixgarbagecyclecyclecyclecyclesufixgarbage",
               "prefixgarbagecyclepadinggarbagecyclesufixgarbage",
               "prefixgarbagecyclecyclepadinggarbageprefixgarbage",
               "prefixgarbagecyclecyclecycleroundroundroundprefixgarbage",
               "abcdefghijklmnopqrstuvqxyz"];

for input in testStrings:

 repCountMax = 0
 longestCycle = ""
 repCount = 0
 for i in range (1, len(input)):
  for j in range( i+1, len(input)):
    substring = input[i:j]
    #print substring
    ls = len(substring)
    repCount = 1
    k = j
    while(substring == input[k:k+ls]):
      k = k + ls
      repCount = repCount +1
      #print "repetition ", repCount, " of ", substring, "\n"
    if (repCount > repCountMax) or ((repCount == repCountMax) and len(substring) > len(bestCycle)):
      repCountMax = repCount
      bestCycle = substring

 if repCountMax > 1:
  print "best cycle in '", input, "' is '", bestCycle,"' which is repeated ", repCountMax, " times."
 else:
  print "no repeated cycles found in string ", input

结果输出：

'prefixgarbagecyclecyclecyclecyclecyclesufixgarbage'中的最佳循环是'ecycl'，重复4次。

“prefixgarbagecyclepadinggarbagecyclesufixgarbage”中的最佳循环是“g”，重复 2 次。

'prefixgarbagecyclecyclepadinggarbageprefixgarbage'中的最佳循环是'ecycl'，重复2次。

“prefixgarbagecyclecyclecyclecycleroundroundroundprefixgarbage”中的最佳循环是“ecycl”，重复 3 次。

在字符串 abcdefghijklmnopqrstuvqxyz 中未发现重复循环

注意 - 找到的循环是ecycl，不是cycle。ecycl首先发生...

第二个注意事项 - 当你不能再“击败”当前的最佳估计时，你可以通过停止来稍微提高效率 - 例如，如果你已经找到了五个重复，并且给定你正在搜索的字符串的大小，则没有' t 空间六次重复。当有大量重复时，这将提高速度。请参阅 Evgeny 的解决方案以了解实现该方法的方法。

于 2013-09-13T18:46:16.080 回答
1

从左到右扫描。

您需要一些键/值对。关键是一封信。该值包括在扫描中找到到该点的字母的最后一个实例的索引以及有关该字母属于两个或多个字符串的任何循环的信息（该列中以该字母开头的最后一个）。

您需要一个地方来存储有关找到的任何周期的信息。称之为“自行车商店”。

当您扫描时，在每个索引处执行此操作：

  • 使用那里的字母。看看它是否在密钥表中。
  • 如果找到，请查看以下字母是否与在表中找到的字母（上一次出现）和此字母（在当前扫描索引处）之间的字母匹配。
  • 如果它们匹配，我们就有一个循环，看看前一次出现是否有信息表明这是存储的循环信息的延续。（注意：相邻字母可能是特殊情况。）
  • 如果是续集，
    • 添加到存储的周期信息以包含这些字符
    • 更新最后一次找到该字母的索引
    • 在循环商店中更新有关此循环的信息
  • 如果不是延续
    • 创建（或替换）存储的周期信息以显示此新周期（计数 = 2）
    • 更新最后一次找到该字母的索引
    • 在自行车商店中添加有关此自行车的信息
  • 如果此事件之后的字母与该事件之后的字母不匹配，
    • 删除这封信的所有存储周期信息
    • 更新最后一次找到该字母的索引
  • 如果该字母不在表中，则为该字母和该索引添加一个键/值对。

完成扫描后，查看自行车商店，看看哪个占主导地位。

请注意，您可能不必将所有循环存储到最后，但对于我来说，如何决定可以丢弃哪些循环并不明显。可能是关于根据键/值对表的内容以及迄今为止占主导地位的内容来保留仍然可能继续的那些。

于 2013-09-13T18:58:46.830 回答
0

我认为可以在这里应用 KMP 算法的修改形式。

从头开始遍历字符串。

拿第一封信，把它存起来。取下一个字母，如果相同，则有 2 个候选重复循环，否则将其添加到现有字符串中。

基本上，在每个字母处，您都会有一个可能的子串列表，用于重复的可能性。当然，您必须跟踪长度和最大编号。直到那时为止的重复。

如果我没记错的话，这可以在 O (n) 时间内完成。

于 2013-09-13T18:51:45.983 回答