小牛快传
题目 小牛快传
思路分析
将原始字符串先存好
因为要保留换行符 所以用getline （遇到换行停止） 一停止就手动添加一个'\n'
然后把字符串过滤出来（去除非字母和统一变小写）
为了后续还原 记录一下在原串的位置
然后就是对过滤后的字符串进行查找最大回文子串
使用中心扩展算法（本质双指针 不过前后、对撞指针都见了 这种向两边的倒是第一次见）
基本思想是将字符串中的每一个字符或字符对视为潜在的回文中心，然后向两边扩展，以检查最长的回文子串 考虑两种情况：
奇数长度的回文： 这时，回文中心是一个字符。例如，在字符串 "racecar" 中，中心是 "e"，回文是整个字符串。
偶数长度的回文： 这时，回文中心是两个字符之间的空隙。例如，在字符串 "abba" 中，中心在两个 "b" 字符之间。
这样可以得到最大回文串的最左和最右
长度就是他们相减+1
把它们映射回原字符串的位置 从原始字符串中截取出来
就是要的结果了
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<int> indexes; // 存储过滤后每个字符在原始字符串中的位置
string filter(const string& str) {
string res;
for (int i = 0; i < str.size(); ++i) {
auto c = str[i];
if (isalpha(c)) {
res += tolower(c);
indexes.push_back(i); // 记录当前字符在原始字符串中的位置
}
}
return res;
}
// 寻找最大回文子串的辅助函数
PII findLongestPalindrome(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return {left + 1, right - 1};
}
int main()
{
string input, line;
while (getline(cin, line)) {
input += line + '\n'; // 保留换行符 getline的妙用
}
string filtered = filter(input);
int start = 0, end = 0; // 最大回文子串在过滤后字符串中的位置
/*
中心扩展算法 找输入字符串中的最大回文子串。
基本思想是将字符串中的每一个字符或字符对视为潜在的回文中心，然后向两边扩展，以检查最长的回文子串
考虑两种情况：
奇数长度的回文：
这时，回文中心是一个字符。例如，在字符串 "racecar" 中，中心是 "e"，回文是整个字符串。
偶数长度的回文：
这时，回文中心是两个字符之间的空隙。例如，在字符串 "abba" 中，中心在两个 "b" 字符之间。
*/
//循环遍历字符串中的每个位置 i，对于每个位置，尝试找到以该位置为中心的最长回文子串。
for (int i = 0; i < filtered.size(); ++i)
{
//尝试找到以位置 i 为中心的最长奇数长度回文子串。
//传递相同的索引值 i 给 findLongestPalindrome 函数，意味着中心是单个字符。
auto [left1, right1] = findLongestPalindrome(filtered, i, i);
//尝试找到以位置 i 和 i + 1 之间的空隙为中心的最长偶数长度回文子串。
//传递 i 和 i + 1 作为参数给 findLongestPalindrome 函数，意味着中心是两个字符之间的空隙。
auto [left2, right2] = findLongestPalindrome(filtered, i, i + 1);
//对于每次扩展得到的回文子串，通过比较其长度与当前已知的最长回文子串长度，更新最长回文子串的起始和结束位置。
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
// 使用记录的位置恢复原始回文子串
string result;
int originalStart = indexes[start]; // 映射回原始字符串的起始位置
int originalEnd = indexes[end]; // 映射回原始字符串的结束位置
result = input.substr(originalStart, originalEnd - originalStart + 1);
cout << end - start + 1 << endl; // 输出最大回文子串的长度
cout << result; // 输出最大回文子串
return 0;
}
💬 评论