我认为01.05.md中最长回文子串中Manacher算法时间复杂度不是O(N),应是O(N^2)

[hongsenliu]

我认为01.05.md中最长回文子串中Manacher算法时间复杂度不是O(N),应是O(N^2).
N是原始输入string的长度，加了分隔符#之后是2N+1，再加$符号就是2N+2.
例如：s="1234321". N=7, 加了两种分隔符后是2N+2=16， s1="$#1#2#3#4#3#2#1#"
外层的for loop, 当i=8，里面的while loop要循环7次。 所以我认为时间复杂度是O(N^2).
请勘校。

[ZumiKua]

当一个回文串的右边界超过mx以后，mx会被更新至该右边界，而后续的while loop均会在mx之后进行查找。实际上，当一个字符被while loop访问以后，mx会被更新至该字符之后，进而所有的while loop会在该字符之后进行查找，所以一个字符仅会被while loop访问一次（仅指通过s[i + p[i]]访问的部分），故该算法的时间复杂度为O(n)。如果不理解的话，也可以自己写个程序测试一下while循环执行的次数，相信你会弄懂的;)

[ArtixZ]

mx 之外的字符 不会被更新至字符之后. 我认为应该是会重复访问字符的