题目描述给定一个字符串s找到s中最长的回文子串。回文串是指正着读和反着读都一样的字符串。输入描述输入一行字符串s长度不超过 1000。输出描述输出s中最长的回文子串。如果存在多个长度相同的最长回文子串输出第一个出现的。示例 1输入textbabad输出textbab说明aba也是有效答案但bab是第一个出现的最长回文子串。示例 2输入textcbbd输出textbbC 解法中心扩展法cpp#include bits/stdc.h using namespace std; int main() { string s; cin s; int n s.size(); int start 0, maxLen 1; auto expand [](int left, int right) { while (left 0 right n s[left] s[right]) { left--; right; } return right - left - 1; }; for (int i 0; i n; i) { int len1 expand(i, i); int len2 expand(i, i 1); int len max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } cout s.substr(start, maxLen) endl; return 0; }
题目描述给定一个字符串s找到s中最长的回文子串。回文串是指正着读和反着读都一样的字符串。输入描述输入一行字符串s长度不超过 1000。输出描述输出s中最长的回文子串。如果存在多个长度相同的最长回文子串输出第一个出现的。示例 1输入textbabad输出textbab说明aba也是有效答案但bab是第一个出现的最长回文子串。示例 2输入textcbbd输出textbbC 解法中心扩展法cpp#include bits/stdc.h using namespace std; int main() { string s; cin s; int n s.size(); int start 0, maxLen 1; auto expand [](int left, int right) { while (left 0 right n s[left] s[right]) { left--; right; } return right - left - 1; }; for (int i 0; i n; i) { int len1 expand(i, i); int len2 expand(i, i 1); int len max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } cout s.substr(start, maxLen) endl; return 0; }
