字符串與算法題詳解：最長回文子串、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(n2)	枚舉中心點，向兩邊擴展	數據量小
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。
• 蛇形矩陣：數學找規律。
• 字符串加密：構造映射表。

掌握這些題目的思路和實現，可以幫助我們快速解決更多字符串相關問題。