枚举算法-最长回文子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-22 20:09:36
 * 最后修改: 2025-01-22 23:21:59
 * 文件描述: brute force enumeration to find the longest palindrome
****************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
char s[maxn];
int lens,ans,odd[maxn],even[maxn];
int main(){
    scanf("%s",s+1);
    lens=strlen(s+1);
     memset(odd, 0, sizeof(odd));
    memset(even, 0, sizeof(even));
    // 遍历字符串，寻找每个字符为中心的最长回文子串
    for(int i=1;i<=lens;i++){
        // 检查以当前字符为中心的奇数长度回文子串
      for(int j = 0; i - j >= 1 && i + j <= lens; j++){
        // 如果发现字符不匹配，记录回文半径并跳出循环
        if(s[i-j]!=s[i+j]){
            odd[i]=j;
            break;
        } 
        else{
        odd[i]=j+1;
        }
      }
      // 检查以当前字符和下一个字符为中心的偶数长度回文子串
      for(int j=0;i - 1 - j >= 1 && i + j <= lens;j++){
        // 如果发现字符不匹配，记录回文半径并跳出循环
        if(s[i-1-j]!=s[i+j]){
            even[i]=j;
            break;
        }
        else{
        even[i] = j + 1;  // 若未退出，则更新回文半径
        }
    }
    
       ans = max(ans, max(2 * odd[i] - 1, 2 * even[i]));        
    }
    cout << ans << endl;
    return 0;
}