@[鏡音リン](/space/show?uid=28913) 你暴力拓展的时候不也是每拓展一**下**右边界就增加一次？所以右边界增加 $O(n)$ 次啊。除了暴力拓展的其他情况都是 $O(1)$ 的，复杂度显然 $O(n)$ 啊……这个复杂度的计算我觉得和MP差不很多？
by 一扶苏一 @ 2018-12-16 09:35:14
@[一扶苏一](/space/show?uid=65363) 不是拓展右边界啊，我指的是
↓某字符串中的左右边界
|-------------**mid**-------**i**-----**maxright**|
↑这种$i$在$maxright$左边，虽然知道有$r[i]>=min(r[mid*2-i],maxright-i)$但毕竟还要再往两边继续拓展一下啊
```cpp
while(s[i+r[i]]==s[i-r[i]])++r[i];
```
也就是还要跑上面这个，这就不是$O(1)$了吧
by Utsuji_risshū @ 2018-12-16 09:57:38
@[鏡音リン](/space/show?uid=28913)
~~说实话我没看懂您的r[i]是啥~~
如果您 $r_i$ 指的是回文半径的话，您执行完这一句难道不应该再加一句
``maxright = std::max(maxright, r[i])``嘛……
这样右端点的移动还是 $O(n)$ 的哇
by 一扶苏一 @ 2018-12-16 10:06:50
啊 那里``r[i]``应该改成``r[i] + i`` 如果您左闭右开可能还要-1？我懒得算了不过差不多就这个意思qwq
by 一扶苏一 @ 2018-12-16 10:08:13
@[一扶苏一](/space/show?uid=65363) $maxright = std::max(maxright, r[i])$这个不一定右端点就动了啊，可能我$r_i$确实算出来了，但加上$i$也没比$maxright$大。
by Utsuji_risshū @ 2018-12-16 10:22:25
然后发现有人做实验说平均每个字符最坏要循环5次所以是$O(n)$,感觉这个很迷。。
by Utsuji_risshū @ 2018-12-16 10:23:51
@[鏡音リン](/space/show?uid=28913) 害怕……不会我马拉车写的是错的吧……
我写的马拉车如果当前中心的回文右端点小于 $maxright$ 的话，显然对称位置的串的回文左端点大于当前 $maxright$ 关于 $mid$ 的对称点。这是个充要条件，反过来也成立，所以如果要判断当前的右端点是否小于 $maxright$ 的话直接 $O(1)$ 看对称点的左端点就好了啊……您说这种情况是 $O(1)$ 的啊……
by 一扶苏一 @ 2018-12-16 10:37:04
@[一扶苏一](/space/show?uid=65363) 突然明白为什么$O(1)$了。谢谢奆佬~
by Utsuji_risshū @ 2018-12-16 10:51:35
@[鏡音リン](/space/show?uid=28913) 没事qwq 我好弱的
by 一扶苏一 @ 2018-12-16 10:58:15