查找给定字符串的主要循环子字符串

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

循环子字符串：

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

主要的循环子字符串：

具有最相邻重复的子串是占优势的

（相邻的重复次数相等）

最长的子串是占主导地位的

（关于长度和相邻重复的关系）

首先出现的子串是占优势的

例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>因为没有重复的相邻子字符串

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

---

找不到比这个二次时间算法更好的东西（用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（N2 / R），其中R是主导子串的重复次数。 空间复杂度是O（1）。

---

从左到右扫描。

你需要一些键/值对。 关键是一封信。 该值包括在扫描时发现的该字母的最后一个实例的索引，以及关于该字母属于两个或更多个字符串（最后一个以该字母中该字母开头）的任何周期的信息。

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

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

用那里的那封信。 看看它是否在按键表中。

如果找到，请查看下列字母是否与表中找到的字母（前一次出现）和该字母（在当前扫描索引处）之间的字母匹配。

如果他们匹配，我们有一个循环，看看以前的事件是否有信息显示这是存储周期信息的延续。 （注意：相邻的字母可能是特殊情况。）

如果是延续，

添加到存储的周期信息以包含这些字符

更新最后发现的这封信的索引

在周期存储中更新关于此周期的信息

如果它不是延续

创建（或替换）存储的周期信息以显示此新的周期（计数= 2）

更新最后发现的这封信的索引

在循环存储中添加关于此循环的信息

如果发生后的字母与发生后的字母不匹配，

删除此字母的任何存储的周期信息

更新最后发现的这封信的索引

如果该字母不在表格中，请为此字母和此索引添加一个键/值对。

完成扫描后，查看周期存储以查看哪个占主导地位。

请注意，你可能不需要存储所有的循环直到结束，但它对我来说并不明显，直到如何决定哪些可以扔掉。 可能有一些关于保持仍然可能继续基于键/值对表的内容加上占主导地位的内容的内容。

---

这是一种可能的方法（由于您的周期必须相邻这一事实而变得更简单）。 选择一个字符串。 看看它是否重复。 跟踪最重复的一个。

编辑实际测试的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

结果输出：

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

'prefixgarbagecyclepadinggarbagecyclesufixgarbage'中的最佳周期是重复2次的'g'。

'prefixgarbagecyclecyclepadinggarbageprefixgarbage'中的最佳周期是'ecycl'，重复2次。

'prefixgarbagecyclecyclecycleroundroundpreprefixgarbage'中的最佳周期是重复3次的'ecycl'。

在字符串abcdefghijklmnopqrstuvqxyz中找不到重复的周期

注 - 找到的周期是ecycl ，而不是cycle 。 ecycl首先发生...

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

链接地址: http://www.djcxy.com/p/70659.html

上一篇: Find the dominant cyclic substring of a given string

下一篇: Algorithm for finding first repeated substring of length k