我正在尝试找到一种算法，该算法可以返回较大循环字符串中最短循环子字符串的长度。
循环字符串将被定义为两个或多个相同字符串的串联，例如“abababab”或“aaaa”...
现在在给定的字符串 T = "abbcabbcabbcabbc"中有一个循环模式 "abbc"但最短的循环子字符串将是 "bb"。
最佳答案
如果您只是寻找出现不止一次的子串:
构建一个 Suffix tree来自字符串。
在创建后缀树时，可以统计每个子串的重复出现次数，保存在节点上出现的次数。
然后就做一个BFS search在树上(这将为您提供分层搜索，从较短的字符串到较长的字符串)并找到第一个大于 1 且出现不止一次的子字符串。
总复杂度:O(n) 其中 n 是字符串的长度
编辑:
The paths from the root to the leaves have a one-to-one relationship with the suffixes of S
您可以实现每个节点包含一个字母的树，这将为您提供更好的粒度并允许您按长度查看所有子字符串。
这是一棵香蕉的后缀树，其中每个节点都包含一个字母，您可以看到那里有所有子串。
如果您查看 applications后缀树的一部分，您会看到它正是用于此类任务 - 查找有关子字符串的内容。
从根看图，你可以看到所有的子字符串都是从根开始的(BFS列表):
b
a
n
ba
an
na
ban
ana
nan
bana
anan
nana
banan
anana
banana
关于algorithm - 较大循环串中的最小循环子串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6459680/