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

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

前言

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

---

一、最长回文子串问题

什么是回文串？

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

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

思路解析

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

1. 中心扩展法

   • 枚举每一个字符，向两边扩展，判断是否对称。
   • 分为两类：奇数长度（如 ABA）、偶数长度（如 ABBA）。

2. 字符串扩展法（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 算法原理

1. 扩展字符串：在每个字符之间加入 #，并在首尾加上边界字符。
   例如：abba → ^#a#b#b#a#$
   （这里的 ^ 和 $ 是哨兵字符，防止越界）

2. 维护回文半径数组 P：

   • P[i] 表示以位置 i 为中心的回文半径（不含中心）。
   • 例如 P[i] = 3，表示回文子串长度是 2*3+1=7。

3. 利用对称性加速：

   • 如果当前位置 i 在已知的最大回文右边界 R 内，那么 P[i] 可以通过对称点的结果推导。
   • 否则就从中心向两边扩展。

4. 求解最大值：

   • 最长回文子串的长度就是 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;}
}

---

五、字符串加密

加密规则

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

示例

密钥：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;
}

---

总结

本文从几个典型题目出发，系统性讲解了字符串相关的算法题：

• 最长回文子串：中心扩展法、字符串扩展。
• IP 地址与整数转换：移位运算与掩码处理。
• 字符串排序：利用 sort。
• 蛇形矩阵：数学找规律。
• 字符串加密：构造映射表。

掌握这些题目的思路和实现，可以帮助我们快速解决更多字符串相关问题。