实验八 算法(学习通）编程题1. 最长回文子串 |
您所在的位置：网站首页 › 找到一个字符串的最长回文字符串 › 实验八 算法(学习通）编程题1. 最长回文子串 |
实验八 算法(学习通）编程题1. 最长回文子串
|
【问题描述】 给定一个字符串，求该字符串中包含的最长回文子串。 输出起始位置最小的位置编号(从0开始)以及回文子串的长度。 【输入形式】 输入的第一行为一个整数T，表示有T组测试数据，接下来的T行，每行一个字符串，对应每组测试数据 【输出形式】 输出有T行，每行两个整数，分别表示对应测试用例中包含的最长回文子串的起始位置(从0开始)和子串长度，如果有多个，则输出起始位置最小的。 【样例输入】 2 12abcbats qwerabccbaw【样例输出】 2 5 4 6【思路分析】 本题可用动态规划，但耗时会比较长。接下来我给大家介绍中心扩展方法，该方法我在练习七 字符串编程题12. E-mail地址一文中曾介绍过。 中心扩展的方法其实就是以字符串的某一子串为中心，向左右进行扩展。例如字符串s = "abacdca"，假设以s[4]为中心，左右进行扩展的时候，如果s[4-1] == s[4+1]，那么"cdc"为回文子串，如果我们再进一步扩展，s[4-2] == s[4+2]，那么"acdca"为回文子串。一般的，我们令 注意回文中心可能为一个字符，也可能为两个字符。 #include using namespace std; int main() { int t, l, r, resL, len; cin >> t; string s; while (t--) { len = 0; cin >> s; //回文中心为一个字符 for (int i = 0; i < s.length(); ++i) { l = r = i; while (l >= 0 && r < s.length() && s[l] == s[r]) { l--; r++; } if (r - l - 1 > len) { len = r - l - 1; resL = l + 1; } } //回文中心为两个字符 for (int i = 0; i < s.length() - 1; ++i) { l = i; r = l + 1; while (l >= 0 && r < s.length() && s[l] == s[r]) { l--; r++; } if (r - l - 1 > len) { len = r - l - 1; resL = l + 1; } } cout |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |