F05 Manacher(马拉车)

/*
重点
1回文半径d[il: 以i 为中心的最长回文串的长度的一半维护右端点最靠右的盒子，
2盒内加速
3盒外暴力
4原串的最长回文串 = 新串的最大半径-1。
时间复杂度: O(n)
*/
#include<bits/stdc++.h>
using namespace std;

const int N=110000;

char s[2*N],a[N];
int d[2*N],n;
void get_d()
{
	n=strlen(a+1);
	s[0]='$';s[2*n+1]='#';
	for(int i=1;i<=n;i++)s[2*i-1]='#',s[2*i]=a[i];
	n=2*n+1;
	memset(d,0,sizeof(d));d[1]=1;
	for(int i=2,L=1,R=1;i<=n;i++)
	{
		if(i<=R) d[i]=min(d[R-i+L],R-i+1);
		while( s[i-d[i]]==s[i+d[i]] ) d[i]++;
		if(i+d[i]-1>R) L=i-d[i]+1,R=i+d[i]-1;
	}
}
int main()
{
    while(scanf("%s",a+1)!=EOF)
    {
    	get_d();
    	int ans=0;
    	for(int i=1;i<=n;i++) ans=max(d[i]-1,ans);
    	printf("%d\n",ans);
    }
    return 0;
}

hansang:

#include<bits/stdc++.h>
using namespace std;

const int N = 11e6 + 10; 

char s[2 * N], ss[N];  
int d[2 * N], n;    
// d[i]: 表示以 i 为中心的最长回文串向两边扩展的长度（包含中心点）
// 例如：对于字符串 "#a#b#a#"，d[4] = 4（以 'b' 为中心的回文 "#a#b#a#"）

void get_d() {
    // 开头结尾添加边界字符防止越界
    s[0] = '$';          
    s[2 * n + 1] = '#'; 
    
    // 在原始字符串的每个字符间插入'#'，统一处理奇偶回文
    // 例如："abc" -> "$#a#b#c#"
    // "abcd" -> "$#a#b#c#d#" 
    // 这样大家的长度都是奇数了 （不包括 0 的边界） 
    for (int i = 1; i <= n; i ++) {
        s[2 * i - 1] = '#'; 
        s[2 * i] = ss[i];   
    } 
    
    n = 2 * n + 1;
    
    memset(d, 0, sizeof(d));
    d[1] = 1;  // 初始化第一个有效位置（索引 1）的回文半径
    
    
    // l、r：当前已知最右回文边界的左端点和右端点 
    // 这个最右回文 [l, r] 就是一个右端点在最右边的回文字串，中心点是 (l + r) / 2  
    // [l, r] 构成一个"盒子"，用于加速后续计算
    
    for (int i = 2, l = 1, r = 1; i <= n; i ++) {
        // 如果 i 在当前最右回文边界内，"盒内加速"
        if (i <= r) {
            /*
            r - i + L 是 i 关于当前回文中心 (l + r) / 2 的对称点
            d[r - i + L] 是对称点的回文半径，因为整个 [l, r] 据回文中心对称，所以可以直接用 
            r - i + 1 是 i 到右边界 r 的距离
            取两者最小值作为 d[i] 的初始值（就是差不多 EXKMP 那样） 
            
            那么为什么不取 i 到回文中心的值一起做最小值呢？ 
            因为两边对称，所以 i 的回文半径 d[i] 是可以越过回文中心的 
            */
            d[i] = min(d[r + l - i], r - i + 1);
        }
        
        // "盒外暴力" 
        while (s[i - d[i]] == s[i + d[i]]) {
            d[i] ++;    // 扩展成功，回文半径 + 1
        }
        
        if (i + d[i] - 1 > r) {
            l = i - d[i] + 1;  // 新盒子的左边界
            r = i + d[i] - 1;  // 新盒子的右边界
        }
    }
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0);                   
    
    while (cin >> ss + 1) { 
	    n = strlen(ss + 1);
	    get_d(); 
	    
	    // 找出最长回文子串的长度
	    int ans = 0;
	    for (int i = 1; i <= n; i ++) { 
	        // 原串 "aba" -> 预处理串 "#a#b#a#"
	        // d[4] = 4（以 'b' 为中心），原串回文长度 = 4 - 1 = 3
	        // 严谨的来说，如果 d[i] 是偶数，那么回文半径一定长这样：#&#&#i（i 是实义字符） 
			// 实义字符的个数为：(d[i] / 2) * 2 - 1，直接 - 1 就好 
	        // 如果 d[i] 是奇数，那么回文半径一定长这样：#&#&i （i 是 #） 
	        // 实义字符的个数为：(d[i] / 2) * 2 - 1，也是直接 - 1 就好 
	        ans = max(d[i] - 1, ans);
	    }
	    
	    cout << ans << "\n"; 
	}
    
    return 0;
}