题目描述：
该题目是一道密码加密题，密码混合在复杂字符串中，是一个对称子字符串，比如12321AABC，则真正要提取的是12321，因为它是对称的，所以需要写一个程序来实现快速的提取。
题目要求提取最长的密码长度。
输入描述：
输入一个字符串
输出描述：
返回有效密码串的最大长度
示例：
输入：
12321AABC
输出：
5
解题思路：
该题其实应该属于动态规划，若某字符串存在某段回文，则将该字符串反转后，该回文依然存在，基于此逻辑可建立二分图，一层层寻找最长的重复子字符串，但是该方法的弊端就是空间复杂度太高了，放在这个题目了没法AC。
只能采用暴力破解了，从左右侧循环分析，固定某段字符串，将其两头缩进判断，若存在非对称点，则跳出并判断该段不是回文；若找到某段字符串是回文，跳出一层循环，因为该层循环下即使再找到回文也是更短的，你品你细品；最后输出最大值，完成。
测试代码：
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ string str; vector<int> result; while(cin>>str){ int maxn=1,flag=0; //暴力循环，分别从左右侧分析 for(int i=0;i<str.length();i++){ for(int j=str.length()-1;j>i;j--){ //flag为0则说明该段是回文 flag=0; int l,r; //判断该段是否为回文 for(l=i,r=j;l<=(i+j)/2;l++,r--){ if(str[l]!=str[r]){ flag=1; break; } } //若该长段为回文，则此级遍历进行下去也只能找到更短的回文，为提速可直接跳出循环 if(flag==0){ maxn=max(maxn,(j-i+1)); break; } } } result.push_back(maxn); } for(auto i:result) { cout<<i<<endl; } return 0; }
动态规划的解法：
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; int CalcSymStringMaxLength(string str) { string left = str; reverse(str.begin(), str.end()); // 反转字符串，若存在回文，则str与反转后的str存在同一子字符串 string right = str; int len1 = left.size(); int len2 = right.size(); int max = 0; int** bp = new int* [len2]; if (len1 == 0) { return 0; } if (len1 == 1) { return 1; } // 建立二分图 for (int i = 0; i < len2; i++) { bp[i] = new int [len1]; } for (int i = 0; i < len2; i++) { if (left[0] == right[i]) { bp[i][0] = 1; } else { bp[i][0] = 0; } } // 先确定边缘信息 for (int i = 0; i < len1; i++) { if (left[i] == right[0]) { bp[0][i] = 1; } else { bp[0][i] = 0; } } for (int i = 1; i < len1; i++) { for (int j = 1; j < len2; j++) { if (left[i] == right[j]) { // 若bp[i - 1][j - 1]有值，则说明之前有一个回文，在此基础上再加1；若无值，相当于给bp[i][j]赋1 bp[i][j] = bp[i - 1][j - 1] + 1; } else { bp[i][j] = 0; } // 刷新最大值 if (bp[i][j] > max) { max = bp[i][j]; } } } return max; } //主函数 int main () { string str; vector<int> result; while (cin >> str) { int temp=CalcSymStringMaxLength(str); result.push_back(temp); } for(auto i:result) { cout<<i<<endl; } return 0; }
动态规划的解法之所以空间不够，主要是因为用二维数组存放了太多数据，若字符串非常大时，这个数组也特别特别大，但是这个解法是最符合题意的，暴力破解太无脑了。。。
