字符串与算法题详解：最长回文子串、IP 地址转换、字符串排序、蛇形矩阵与字符串加密

前言

在编程题训练中，字符串相关的题目非常常见。本文将结合几个典型的例题，详细解析它们的解题思路和实现方式，帮助初学者循序渐进地掌握常用技巧。

一、最长回文子串问题

什么是回文串？

回文串（Palindrome）就是正读和反读相同的字符串，例如：

ABA 是回文串
ABBA 也是回文串
ABC 不是回文串

思路解析

要找出一个字符串中最长的回文子串长度，常见方法有两种：

中心扩展法
- 枚举每一个字符，向两边扩展，判断是否对称。
- 分为两类：奇数长度（如 ABA）、偶数长度（如 ABBA）。
字符串扩展法（Manacher 算法思想）
- 在字符串中插入特殊字符（如 #），统一处理奇数和偶数回文的情况。

代码实现（中心扩展法）

#include <iostream>
#include <string>
using namespace std;int longestPalindrome(string s) {int n = s.size();int maxLen = 1;for (int i = 0; i < n; i++) {// 奇数回文int l = i, r = i;while (l >= 0 && r < n && s[l] == s[r]) {maxLen = max(maxLen, r - l + 1);l--, r++;}// 偶数回文l = i, r = i + 1;while (l >= 0 && r < n && s[l] == s[r]) {maxLen = max(maxLen, r - l + 1);l--, r++;}}return maxLen;
}int main() {string s;cin >> s;cout << longestPalindrome(s) << endl;
}

示例

输入：

babad

输出：

3   // 最长回文子串是 "bab" 或 "aba"

好的，你提到的 字符串扩展法（Manacher 算法思想） 是解决最长回文子串问题的经典算法。下面我帮你详细补充到教程里。

二、字符串扩展法（Manacher 算法思想）

核心思路

在使用中心扩展法时，我们需要分别处理：

奇数长度回文串（如 ABA）
偶数长度回文串（如 ABBA）

为了统一处理，可以在字符串中插入特殊字符（例如 #），让所有回文子串都变成奇数长度。
比如原始字符串 abba，扩展后变成：

# a # b # b # a #

这样：

原本的 abba（偶数回文）变成了 #a#b#b#a#，长度为奇数；
原本的 aba（奇数回文）变成了 #a#b#a#，仍然是奇数。

这样就可以只写一份扩展逻辑，统一处理。

Manacher 算法原理

扩展字符串：在每个字符之间加入 #，并在首尾加上边界字符。
例如：abba → ^#a#b#b#a#$
（这里的 ^ 和 $ 是哨兵字符，防止越界）
维护回文半径数组 P：
- P[i] 表示以位置 i 为中心的回文半径（不含中心）。
- 例如 P[i] = 3，表示回文子串长度是 2*3+1=7。
利用对称性加速：
- 如果当前位置 i 在已知的最大回文右边界 R 内，那么 P[i] 可以通过对称点的结果推导。
- 否则就从中心向两边扩展。
求解最大值：
- 最长回文子串的长度就是 max(P[i]) - 1（因为扩展时多加了 #）。

代码实现（C++）

#include <iostream>
#include <string>
#include <vector>
using namespace std;string preprocess(const string &s) {string t = "^";for (char c : s) {t += "#" + string(1, c);}t += "#$";return t;
}int longestPalindrome(string s) {string t = preprocess(s);int n = t.size();vector<int> P(n, 0);int C = 0, R = 0; // C: 当前回文中心, R: 当前回文最右端for (int i = 1; i < n - 1; i++) {int mirror = 2 * C - i; // i 关于中心 C 的对称点if (i < R)P[i] = min(R - i, P[mirror]);// 中心扩展while (t[i + 1 + P[i]] == t[i - 1 - P[i]])P[i]++;// 如果扩展后超过了 R，则更新中心和右边界if (i + P[i] > R) {C = i;R = i + P[i];}}// 找到最大回文半径int maxLen = 0;for (int len : P)maxLen = max(maxLen, len);return maxLen;
}int main() {string s;cin >> s;cout << longestPalindrome(s) << endl;
}

示例

输入：

abba

扩展后：

^#a#b#b#a#$

最终输出：

4   // 最长回文子串是 "abba"

方法对比

方法	时间复杂度	思路	适用场景
中心扩展法	O(n²)	枚举中心点，向两边扩展	数据量小
Manacher 算法	O(n)	扩展字符串 + 回文半径数组	大数据量

二、整数与 IP 地址的转换

基本原理

IP 地址由四个数字组成（如 10.0.3.193），每个数字占 8 位，总共 32 位。
可以将其转化为一个 32 位整数。

例如：

10.0.3.193 → (10 << 24) + (0 << 16) + (3 << 8) + 193

代码实现

#include <iostream>
using namespace std;int main() {unsigned int a, b, c, d;char dot;cin >> a >> dot >> b >> dot >> c >> dot >> d;unsigned int ip = (a << 24) + (b << 16) + (c << 8) + d;cout << ip << endl;unsigned int num;cin >> num;cout << ((num >> 24) & 255) << "."<< ((num >> 16) & 255) << "."<< ((num >> 8) & 255) << "."<< (num & 255) << endl;
}

三、字符串排序

题目解析

给定一个字符串，要求按 ASCII 值升序排序。

代码实现

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;int main() {string s;cin >> s;sort(s.begin(), s.end());cout << s << endl;
}

示例

输入：

dcba321

输出：

123abcd

四、蛇形矩阵（找规律问题）

问题描述

输入一个整数 n，构造一个 n × n 的蛇形矩阵，只输出上三角部分。

例如 n = 5 时：

1  3  6  10 15
2  5  9  14
4  8  13
7  12
11

思路

第 1 行输出 1 开始，每个元素与前一个差值依次增加。
每行输出的数字个数递减。

代码实现

#include <iostream>
using namespace std;int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {int num = i;for (int j = i; j <= n; j++) {cout << num << " ";num += j;}cout << endl;}
}

五、字符串加密

加密规则

选择一个单词作为密钥，去掉重复字母。
用密钥替换字母表前缀，构造加密字母表。
明文中的每个字母替换为加密表对应字母。

示例

密钥：attack
明文：attack
加密：txyz...

代码实现

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;int main() {string key, text;cin >> key >> text;string dict;bool used[26] = {false};for (char c : key) {if (!used[c - 'a']) {dict += c;used[c - 'a'] = true;}}for (char c = 'a'; c <= 'z'; c++) {if (!used[c - 'a']) dict += c;}unordered_map<char, char> mp;for (int i = 0; i < 26; i++) {mp['a' + i] = dict[i];}for (char c : text) {if (islower(c)) cout << mp[c];else if (isupper(c)) cout << (char)toupper(mp[tolower(c)]);else cout << c;}cout << endl;
}