马拉车(manacher)算法

马拉车算法是回文串处理方面的一个算法。初学者一开始看有些不容易懂。这里试着补充说明一下。一些简单重复的东西就不啰嗦了。 只做一下3种情况的分类讨论说明。

综合以上三种情况，代码如下:

if(Len[2 * id - i] < mx - i && i < mx ) Len[i] = Len[2 * id - i]; else { Len[i] = (i < mx)?mx - i:1; while(str[i - Len[i]]== str[i + Len[i]]) Len[i]++; }

看别人的实现，因为把前两种情况合并起来三元表达式了，所以就把扩展检测放在了判断之外。无论需不需要扩展检测都做了扩展检测。结果不会错，但是初学者估计容易看不清楚。