不同旋转字符串的数量

Question

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

例如 :-

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

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

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

Answer 1

后缀树,宝贝!

如果string是S.构造SS的后缀树(S连接到S).

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

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