---
title: "小牛快传"
created: 2025-11-28
tags:
  - 算法
---

# 小牛快传

## 题目 [小牛快传](https://www.acwing.com/problem/content/description/1417/)

![[image-1a3f6e0f.png]]

## 思路分析

将原始字符串先存好

因为要保留换行符 所以用getline （遇到换行停止） 一停止就手动添加一个'\n'

然后把字符串过滤出来（去除非字母和统一变小写）

为了后续还原 记录一下在原串的位置

然后就是对过滤后的字符串进行查找最大回文子串

使用中心扩展算法（本质双指针 不过前后、对撞指针都见了 这种向两边的倒是第一次见）

基本思想是将字符串中的每一个字符或字符对视为潜在的回文中心，然后向两边扩展，以检查最长的回文子串 考虑两种情况：

奇数长度的回文： 这时，回文中心是一个字符。例如，在字符串 "racecar" 中，中心是 "e"，回文是整个字符串。

偶数长度的回文： 这时，回文中心是两个字符之间的空隙。例如，在字符串 "abba" 中，中心在两个 "b" 字符之间。

这样可以得到最大回文串的最左和最右

长度就是他们相减+1

把它们映射回原字符串的位置 从原始字符串中截取出来

就是要的结果了

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[字符串匹配|字符串匹配]] 🏠 [[00-刷题理模型]] ➡️ [[解码|解码]]