假设我们有一个小写字符串 s,我们必须找到在 s 中至少出现两次的最长子字符串的长度。如果我们找不到这样的字符串,则返回 0。
因此,如果输入类似于 s = "abdgoalputabdtypeabd",那么输出将是 3,因为出现不止一次的最长子字符串是 "abd"。
让我们看看以下实现以获得更好的理解 -
def lcs(s1, s2): n = min(len(s1), len(s2)) for i in range(n): if s1[i] != s2[i]: return s1[:i] return s1[:n] def solve(s): suffixes = [] n = len(s) max_len = 0 for i in range(n): suffixes.append(s[i:n]) suffixes.sort() for a, b in zip(suffixes, suffixes[1:]): rtr = lcs(a, b) if len(rtr) > max_len: max_len = len(rtr) return max_len s = "abdgoalputabdtypeabd" print(solve(s))
"abdgoalputabdtypeabd"输出结果
3