最长回文子串问题

参考：最长回文子串问题（五种方法） | 春水煎茶 (writings.sh)

判断回文字符串

暴力O(N2)

bool palin(string s){
	int l = 0;
	int r = s.length();
	while(l < r){
		if(s[l++] != s[r--]) return false;
	}
	return true;
}

求最长回文子子串

暴力枚举O(N4)

int getMaxPalin(string s){
	int len = s.length();
	for(int i = len ; i >= 2 ; i --){
		for(int j = 0 ; j+i-1 < len ; j ++){
			if(palin(s.substr(j,i))) return i;
		}
	}
	return 1;
}

二维动态规划O(N2)

dp[i][j] 表示 [ i, j ]区间内的子串是否为回文串

状态转移方程 \(dp[l][r] = (s[l] == s[r] \&\& dp[l+1][r-1])\)

for(int i = 0 ; i < len ; i ++){
    dp[i][i] = true;
    max_ = 1;
    if(i > 0 && s[i-1] == s[i]){
        dp[i-1][i] = true;
        max_ = 2;
    }
}
for(int i = 3 ; i <= len ; i ++){
    for(int j = 0 ; j+i-1 < len ; j ++){
        int l = j;
        int r = j + i - 1;
        dp[l][r] = (s[l] == s[r] && dp[l+1][r-1]);
        if(dp[l][r]) max_ = max(max_, i);
    }
}

一维动态规划O(N2)

dp[i] 表示以i结尾的最长回文子串的起始位置

int getMaxPalin(string s){
	if(s.empty()) return 0;
	int len = s.length();
	int res = 1;
	dp[0] = 0;
	for(int i = 1 ; i < len ; i ++){
		if(dp[i-1] > 0 && s[i] == s[dp[i-1]-1]){
			dp[i] = dp[i-1]-1;
		}else{
			int l = dp[i-1];
			int r = i;
			int st = l;
			while(l < r){
				if(s[l] == s[r]){
					l++;r--;
				}else{
					l++;r=i;
					st = l;
				}
			}
			dp[i] = st;
		}
		res = max(i - dp[i] + 1, res);
	}
	return res;
}