[hdu 3068|http://acm.hdu.edu.cn/showproblem.php?pid=3068]
- Algorithm:
https://segmentfault.com/a/1190000003914228
const int MaxN = 1000000 + 7;
char ms[MaxN * 2];
int mr[MaxN * 2];
int manacher( char *s ) {
int len = strlen( s ), l = 0;
ms[l++] = '$';
for( int i = 0; i < len; ++i, l += 2 ) {
ms[l] = '#', ms[l + 1] = s[i];
}
ms[l++] = '#';
int mx = 0, mp = 0, ans = 0;
for( int i = 0; i < l; ++i ) {
mr[i] = mx > i ? min( mr[mp * 2 - i], mx - i ) : 1;
while( ms[i + mr[i]] == ms[i - mr[i]] ) mr[i]++;
if( i + mr[i] > mx ) {
mx = i + mr[i], mp = i;
}
ans = max( ans, mr[i] - 1 );
}
return ans;
}
-
Note
填充首末间隙，并且首部再加一个（使整个串S是回文串时失配）\
mr[i] = mx > i ? min( mr[mp * 2 - i], mx - i ) : 1;
while( ms[i + mr[i]] == ms[i - mr[i]] ) mr[i]++;
if( i + mr[i] > mx ) mx = i + mr[i], mp = i;
- 类似尺取，S_i 只进一次 => O(n)
