一、题目

🔸题目描述

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

🔸输入输出

输入
输入一个字符串（字符串的长度不超过2500）

输出
返回有效密码串的最大长度

🔸样例1

输入
ABBA输出
4

🔸样例2

输入
ABBBA输出
5

🔸样例3

输入
12HHHHA输出
4

二、代码参考

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String s = "";while ((s = br.readLine()) != null) {System.out.println(validLen(s));}br.close();}public static int validLen(String s) {int len = s.length();// 状态：对比的两个字符索引起始和终止索引位置// 定义: 字符串s的i到j字符组成的子串是否为回文子串boolean[][] dp = new boolean[len][len];int res = 0;// base casefor(int i = 0; i < len - 1; i++) {dp[i][i] = true;}for(int r = 1; r < len; r++) {for(int l = 0; l < r; l++) {// 状态转移：如果左右两字符相等,同时[l+1...r-1]范围内的字符是回文子串// 则 [l...r] 也是回文子串if(s.charAt(l) == s.charAt(r) && (r-l <= 2 || dp[l+1][r-1])) {dp[l][r] = true;// 不断更新最大长度res = Math.max(res, r - l + 1);} }}return res;}
}--------------------------------------------------------str = input()
n = len(str)
list = []
for i in range(0,n-1):for j in range(1,n):if str[j] == str[i] and str[i+1:j] == str[j-1:i:-1]:list.append(len(str[i:j+1]))
print(max(list))--------------------------------------------------------------#include <stdio.h>
#include <string.h>//颠倒后比较最长字段 XXX
//中心遍历
//增加遍历指针low high是遍历更加简洁
int main()
{char str[3000];scanf("%s", str);int len = strlen(str);int max[len][2];for (int i = 0; i < len; i++){int low, high;//以i为中心奇数串low = i - 1, high = i + 1;max[i][0] = 1;while (low >= 0 && high < len && str[low] == str[high]){low--;high++;max[i][0] += 2;}//以i为中心偶数串low = i, high = i + 1;max[i][1] = 0;while (low >= 0 && high < len && str[low] == str[high]){low--;high++;max[i][1] += 2;}}int maxlen = 0;for (int i = 0; i < len; i++){for (int j = 0; j < 2; j++){if (max[i][j] > maxlen)maxlen = max[i][j];}}printf("%d", maxlen);return 0;
}