Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
分析：求最长的回文子串，时间赋值度n平方；
aaa #a#a#a# 找最小单位: #a# 或者 a#a 然后以最小单位为中心向两边扩充；
int main() { string s; while (cin >> s) { vector<char>cvec; string result; string tmp; int j; int ibest = 0; // 最大长度 int current = 0; //当前长度 size_t beg, end,cbeg,cend; //标记位置（当前/最终） /* 将s进行处理 abcbc #a#b#c#b#c# */ for (int i = 0; i <= s.size(); i++) { tmp.push_back('#'); tmp.push_back(s[i]); } tmp.push_back('#'); s = tmp; //处理后将其赋值给s for (size_t i = 0; i < s.size(); i++) //进行搜索，i每次前进1位 { j = cvec.size(); //进来先查找当前i对应得s[i]是否出现在容器中，以及出现的位置用j标记 while (--j >= 0) { if (cvec[j] == s[i])break; } if (j >= 0 && j + 2 == i) //当j>=0表示在容器中找到相等的，位置为j，而且位置j和i相隔一个单位（我们要找的最小单位）（#c#）第一个#对应j的位置，第二个#对应i的位置 { int k = i; //将i赋值给k，然后以（#c#）即j,k位置为中心向两边扩充 current = 3; //最小单位的长度为3（算了#c#） cbeg = j; cend = k; //当前位置 while (--j >= 0 && ++k < s.size()) // 往两边进行扩充 { if (cvec[j] == s[k]) //如果相等，则当前长度+2，当前位置改变 { current += 2; cbeg = j; cend = k; } else break; //如果不相等，则终止 } } if (current > ibest) //进行比较 { ibest = current; beg = cbeg; end = cend; } cvec.push_back(s[i]); //最后将i处对应得s[i]放入容器，i++进行下一个判断 } /* 对结果进行处理 */ for (auto i = beg; i <= end; i++) { if (s[i] != '#') result.push_back(s[i]); } cout << result << endl; } }