c++ - 如何找到修改后的字符串等于原始字符串的时间

Question

如何解决字符串首先循环旋转 1 个字母，然后旋转 2 个字母，很快，修改后的字符串何时与原始字符串相等的问题？这些字符串仅由“a”和“b”组成。

例如：aabaab 是第一个字母旋转时的字符串，它将在第二次旋转时变为 abaaba，它将变为 aabaab，因此答案为 2。

我试图解决这个问题，但只能通过蛮力来解决。 https://pasteboard.co/HwWR6WZ.png

任何帮助将不胜感激。

标签： c++stringalgorithmc++14

Answer 1

假设s为原始字符串，您想要的是最小索引i > 0，即s字符串中索引处的子i字符串ss。你可以在这棵树中构造then search的后缀树。该算法在 O(n) 时间内运行。sss

例如考虑s = abab, 的后缀树ss, ieabababab看起来像 ($代表一个字符串的结尾)

           root
        ab/    \b
         /      \
      ab/\$    $/\ab
       /  \    /  \
      *    6  7  $/\ab
   ab/\$         /  \
    /  \        5  $/\ab$ 
ab$/\$  4          /  \
  /  \            3    1
 0    2          

搜索后abab我们到达*节点，在​​其子树中有三个叶子代表索引 0,2,4。答案是其中最小的正指数，即2。

可以使用后缀数组和 LCP 数组在 O(n) 时间内构建后缀树。