string - 不同旋转字符串的数量

Question

我们有一个字符串S，我们想计算通过旋转字符串可以形成的不同字符串的数量。

例如:-

S = "aaaa" ，这里是 1 个字符串 {"aaaa"}

S = "abab" ，这里是 2 个字符串 {"abab" , "baba"}

那么，有没有一种算法可以在 O(|S|) 复杂度中解决这个问题，其中 |S|是字符串的长度。

Answer 1

后缀树，宝贝!

如果字符串是 S。构造 SS 的后缀树(S 连接到 S)。

查找长度为 |S| 的唯一子串的数量。您自动获得的独特性。对于长度 |S|您可能需要稍微更改后缀树算法(以保持深度信息)，但这是可行的。

(请注意，johnsoe 的另一个答案实际上是二次的，或者更糟，这取决于 Set 的实现)。