我正在尝试找到一种算法，该算法可以返回较大循环字符串中最短循环子字符串的长度。
循环字符串将被定义为两个或多个相同字符串的串联，例如“abababab”或“aaaa”......
现在在给定的示例中，字符串 T = "abbcabbcabbcabbc" 有一个模式 "abbc" 的循环，但最短的循环子字符串将是 "bb"。
问问题
1483 次
2 回答
1
如果您只是在寻找多次出现的子字符串：
从字符串构建后缀树。
在创建后缀树时，您可以计算每个子字符串的重复出现次数并将其保存在节点上的出现次数上。
然后只需在树上进行BFS 搜索（这将为您提供从较短到较长字符串的分层搜索）并找到第一个长于 1 且多次出现的子字符串。
总复杂度：O(n)，其中 n 是字符串的长度
编辑：
从根到叶子的路径与 S 的后缀是一一对应的关系
您可以实现每个节点包含一个字母的树，这将为您提供更好的粒度并允许您按长度查看所有子字符串。
这是香蕉的后缀树，其中每个节点都包含一个字母，您可以看到那里有所有子字符串。
如果您查看后缀树的应用程序部分，您会发现它正是用于此类任务 - 查找有关子字符串的内容。
从根目录查看图像，您可以看到所有子字符串都从根目录开始（BFS 列表）：
b
a
n
ba
an
na
ban
ana
nan
bana
anan
nana
banan
anana
banana
于 2011-06-23T19:55:54.593 回答
0
让我在您的示例中将生成器称为“abbc” - 即您为了获得更大的字符串而重复的字符串。
第一个观察是较小的字符串应该通过重复一些子字符串两次来制作。
很明显，最小的字符串应该小于重复两次的生成器（2*generator），因为 2*generator 是循环的。
现在请注意，在搜索较小的循环字符串时，您只需要考虑通过生成器 3 次获得的字符串。事实上，如果最小的不存在，但它在 4* 生成器中，那么它必须跨越至少两个生成器，但它不会是最小的。
所以现在让我们假设更大的字符串是 3*generator（或 2*generator）。同样很明显，如果生成器只有不同的数字，那么答案是 2*generator。如果不是，那么您只需要在位置 i 和 j 处找到较大字符串中的所有相同字符对，并检查以 2*(ji) 长的 ai 开头的字符串是否是循环的。如果你按ji增加的顺序尝试它们，那么你可以在第一次成功后停止。
于 2011-06-23T19:48:22.163 回答