UVa 12656 Almost Palindrome

题目描述

给定一行文本，找出其中最长的 “几乎回文” 子串。一个字符串 $S$ 被称为 “几乎回文” ，如果满足：

例如，当 $k=1$ 时，"Race cat" 是几乎回文，因为 $a(S)=\text{"racecat"}$ ，$b(S)=\text{"tacecar"}$ ，它们正好有 $2$ 个位置不同。

输入格式

输入包含最多 $25$ 个测试用例。每个测试用例两行：

• 第一行是一个整数 $k$（$0\le k\le 200$）；
• 第二行是一个字符串，长度不超过 $1000$ 个字符（不含换行符），至少包含一个字母。字符串只包含字母、空格和其他可打印字符（如 , 或 . 等），且不会以空白字符开头。

输出格式

对于每个测试用例，输出一行，格式为 Case x: L P ，其中 $x$ 是测试用例编号（从 $1$ 开始），$L$ 是最长几乎回文子串的长度，$P$ 是该子串的起始位置（从 $1$ 开始计数）。如果有多个长度相同的最长子串，输出起始位置最小的那个。

样例

输入

1
Wow, it is a Race cat!
0
abcdcfg
0
Kitty: Madam, I'm adam.

输出

Case 1: 8 3
Case 2: 1 1
Case 3: 15 8

题目分析

本题的核心是：在给定文本中，找出一个子串，其字母序列与反转后的字母序列在相同位置上的不同字符个数不超过 $2k$ 。子串必须同时以字母开头和结尾，且长度以其在原文本中的实际字符数（包括非字母）为准。

直接枚举所有子串并判断，需要 $O(n^3)$ 或 $O(n^2\cdot L)$ 的时间，其中 $n$ 为原串长度（$\le 1000$），虽然 $n$ 不大，但 $O(n^3)$ 可能超时（最坏 $10^9$ 量级）。我们需要更高效的方法。

观察回文判断的本质：只关心字母序列的对称性。因此，可以先把所有字母提取出来，记录每个字母在原串中的位置。然后问题转化为：在字母序列中找到连续区间 $[l,r]$ ，使得该区间与其反转的对应位置不同的个数 $\text{diff}(l,r)\le 2k$ ，然后计算其对应的原始长度 $\text{pos}[r]-\text{pos}[l]+1$ ，并记录最大的原始长度和最小的起始位置。

解题思路

提取字母与位置映射

遍历原字符串，每当遇到字母时，将其转换为小写，存入数组 $\text{letters}$ ，同时将该字符在原串中的下标（$0$‑based）存入数组 $\text{pos}$ 。这样，原串的任意子串若首尾都是字母，则对应于 $\text{letters}$ 中的一段连续区间 $[l,r]$ ，其原始长度为 $\text{pos}[r]-\text{pos}[l]+1$ ，起始位置为 $\text{pos}[l]+1$ 。

计算区间差异数

我们需要快速得到任意区间 $[l,r]$ 的差异数 $\text{diff}(l,r)$ ，定义为区间内对称位置（$i$ 与 $r-(i-l)$ ）字符不同的个数（每个不同位置贡献 $1$ ，注意对称的两个位置各算一个，故若 $\text{letters}[l+i]\ne \text{letters}[r-i]$ ，则这两个位置都不同，贡献 $2$ ）。

我们使用动态规划预处理所有区间的差异数。设 $\text{dp}[l][r]$ 表示区间 $[l,r]$ 与其反转的差异位置总数。转移关系如下：

• 当区间长度 $len=1$ 时，$\text{dp}[l][l]=0$ ；
• 当 $len\ge 2$ 时，$\text{dp}[l][r]=\text{dp}[l+1][r-1]+(\text{letters}[l]\ne \text{letters}[r])\times 2$ ，其中当 $len=2$ 时，$\text{dp}[l+1][r-1]$ 视为 $0$ 。

按区间长度从小到大计算即可。由于字母个数 $m$ 不超过 $1000$ ，二维数组大小为 $m\times m$ ，时间和空间均可行。

枚举所有合法区间

对于每一对 $0\le l\le r<m$ ，若 $\text{dp}[l][r]\le 2k$ ，则该区间对应的原串子串是一个合法候选。计算其原始长度 $\text{curLen}=\text{pos}[r]-\text{pos}[l]+1$ 和起始位置 $\text{curStart}=\text{pos}[l]+1$ ，并更新全局最优解：优先比较长度，长度相同时取起始位置更小者。

最终输出最优长度和起始位置。

复杂度分析

• 提取字母：$O(n)$ ，其中 $n$ 为原串长度。
• DP 计算：$O(m^2)$ ，$m$ 为字母个数，最大 $1000$ ，约 $10^6$ 次操作。
• 枚举区间：$O(m^2)$ 。
• 总时间复杂度：$O(n+m^2)$ ，空间复杂度：$O(m^2)$ ，完全可以满足题目限制（最多 $25$ 个测试用例）。

代码实现

// Almost Palindrome
// UVa ID: 12656
// Verdict: Accepted
// Submission Date: 2026-06-24
// UVa Run Time: 0.020s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int caseNo = 0, k;
string line;
while (cin >> k) {
getline(cin, line); // 消耗掉 k 后的换行符
getline(cin, line); // 读取原字符串（可能含空格）

vector<char> letters; // 小写字母序列
vector<int> pos; // 每个字母在原串中的位置（0‑based）
for (int i = 0; i < (int)line.size(); ++i)
if (isalpha(line[i])) {
letters.push_back(tolower(line[i]));
pos.push_back(i);
}

int m = letters.size();
vector<vector<int>> dp(m, vector<int>(m, 0));

// 按长度递增计算 dp[l][r]（差异位置总数）
for (int len = 1; len <= m; ++len)
for (int l = 0; l + len – 1 < m; ++l) {
int r = l + len – 1;
if (len == 1) dp[l][r] = 0;
else {
int inner = (len == 2) ? 0 : dp[l + 1][r – 1];
dp[l][r] = inner + (letters[l] != letters[r] ? 2 : 0);
}
}

int bestLen = 0, bestStart = INT_MAX;
int limit = 2 * k;
for (int l = 0; l < m; ++l)
for (int r = l; r < m; ++r)
if (dp[l][r] <= limit) {
int curLen = pos[r] – pos[l] + 1; // 原串中该子串的实际长度
int curStart = pos[l] + 1; // 起始位置（1‑based）
if (curLen > bestLen || (curLen == bestLen && curStart < bestStart)) {
bestLen = curLen;
bestStart = curStart;
}
}

cout << "Case " << ++caseNo << ": " << bestLen << " " << bestStart << "\\n";
}
return 0;
}

总结

本题的关键在于：

该解法在 $n\le 1000$ 的情况下非常高效，代码简洁，易于实现。