题目描述给定一行文本找出其中最长的 “几乎回文” 子串。一个字符串SSS被称为 “几乎回文” 如果满足SSS以字母开头并以字母结尾将SSS中所有非字母字符删除并将所有字母转为小写后得到a(S)a(S)a(S)将a(S)a(S)a(S)反转后得到b(S)b(S)b(S)两者在最多2k2k2k个位置上字符不同。例如当k1k 1k1时Race cat是几乎回文因为a(S)racecata(S) \text{racecat}a(S)racecatb(S)tacecarb(S) \text{tacecar}b(S)tacecar它们正好有222个位置不同。输入格式输入包含最多252525个测试用例。每个测试用例两行第一行是一个整数kkk0≤k≤2000 \le k \le 2000≤k≤200第二行是一个字符串长度不超过100010001000个字符不含换行符至少包含一个字母。字符串只包含字母、空格和其他可打印字符如,或.等且不会以空白字符开头。输出格式对于每个测试用例输出一行格式为Case x: L P其中xxx是测试用例编号从111开始LLL是最长几乎回文子串的长度PPP是该子串的起始位置从111开始计数。如果有多个长度相同的最长子串输出起始位置最小的那个。样例输入1 Wow, it is a Race cat! 0 abcdcfg 0 Kitty: Madam, Im adam.输出Case 1: 8 3 Case 2: 1 1 Case 3: 15 8题目分析本题的核心是在给定文本中找出一个子串其字母序列与反转后的字母序列在相同位置上的不同字符个数不超过2k2k2k。子串必须同时以字母开头和结尾且长度以其在原文本中的实际字符数包括非字母为准。直接枚举所有子串并判断需要O(n3)O(n^3)O(n3)或O(n2⋅L)O(n^2 \cdot L)O(n2⋅L)的时间其中nnn为原串长度≤1000\le 1000≤1000虽然nnn不大但O(n3)O(n^3)O(n3)可能超时最坏10910^9109量级。我们需要更高效的方法。观察回文判断的本质只关心字母序列的对称性。因此可以先把所有字母提取出来记录每个字母在原串中的位置。然后问题转化为在字母序列中找到连续区间[l,r][l, r][l,r]使得该区间与其反转的对应位置不同的个数diff(l,r)≤2k\textit{diff}(l, r) \le 2kdiff(l,r)≤2k然后计算其对应的原始长度pos[r]−pos[l]1\textit{pos}[r] - \textit{pos}[l] 1pos[r]−pos[l]1并记录最大的原始长度和最小的起始位置。解题思路提取字母与位置映射遍历原字符串每当遇到字母时将其转换为小写存入数组letters\textit{letters}letters同时将该字符在原串中的下标000‑based存入数组pos\textit{pos}pos。这样原串的任意子串若首尾都是字母则对应于letters\textit{letters}letters中的一段连续区间[l,r][l, r][l,r]其原始长度为pos[r]−pos[l]1\textit{pos}[r] - \textit{pos}[l] 1pos[r]−pos[l]1起始位置为pos[l]1\textit{pos}[l] 1pos[l]1。计算区间差异数我们需要快速得到任意区间[l,r][l, r][l,r]的差异数diff(l,r)\textit{diff}(l, r)diff(l,r)定义为区间内对称位置iii与r−(i−l)r - (i-l)r−(i−l)字符不同的个数每个不同位置贡献111注意对称的两个位置各算一个故若letters[li]≠letters[r−i]\textit{letters}[li] \ne \textit{letters}[r-i]letters[li]letters[r−i]则这两个位置都不同贡献222。我们使用动态规划预处理所有区间的差异数。设dp[l][r]\textit{dp}[l][r]dp[l][r]表示区间[l,r][l, r][l,r]与其反转的差异位置总数。转移关系如下当区间长度len1len 1len1时dp[l][l]0\textit{dp}[l][l] 0dp[l][l]0当len≥2len \ge 2len≥2时dp[l][r]dp[l1][r−1](letters[l]≠letters[r])×2\textit{dp}[l][r] \textit{dp}[l1][r-1] \big( \textit{letters}[l] \ne \textit{letters}[r] \big) \times 2dp[l][r]dp[l1][r−1](letters[l]letters[r])×2其中当len2len 2len2时dp[l1][r−1]\textit{dp}[l1][r-1]dp[l1][r−1]视为000。按区间长度从小到大计算即可。由于字母个数mmm不超过100010001000二维数组大小为m×mm \times mm×m时间和空间均可行。枚举所有合法区间对于每一对0≤l≤rm0 \le l \le r m0≤l≤rm若dp[l][r]≤2k\textit{dp}[l][r] \le 2kdp[l][r]≤2k则该区间对应的原串子串是一个合法候选。计算其原始长度curLenpos[r]−pos[l]1\textit{curLen} \textit{pos}[r] - \textit{pos}[l] 1curLenpos[r]−pos[l]1和起始位置curStartpos[l]1\textit{curStart} \textit{pos}[l] 1curStartpos[l]1并更新全局最优解优先比较长度长度相同时取起始位置更小者。最终输出最优长度和起始位置。复杂度分析提取字母O(n)O(n)O(n)其中nnn为原串长度。DP 计算O(m2)O(m^2)O(m2)mmm为字母个数最大100010001000约10610^6106次操作。枚举区间O(m2)O(m^2)O(m2)。总时间复杂度O(nm2)O(n m^2)O(nm2)空间复杂度O(m2)O(m^2)O(m2)完全可以满足题目限制最多252525个测试用例。代码实现// Almost Palindrome// UVa ID: 12656// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.020s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intcaseNo0,k;string line;while(cink){getline(cin,line);// 消耗掉 k 后的换行符getline(cin,line);// 读取原字符串可能含空格vectorcharletters;// 小写字母序列vectorintpos;// 每个字母在原串中的位置0‑basedfor(inti0;i(int)line.size();i)if(isalpha(line[i])){letters.push_back(tolower(line[i]));pos.push_back(i);}intmletters.size();vectorvectorintdp(m,vectorint(m,0));// 按长度递增计算 dp[l][r]差异位置总数for(intlen1;lenm;len)for(intl0;llen-1m;l){intrllen-1;if(len1)dp[l][r]0;else{intinner(len2)?0:dp[l1][r-1];dp[l][r]inner(letters[l]!letters[r]?2:0);}}intbestLen0,bestStartINT_MAX;intlimit2*k;for(intl0;lm;l)for(intrl;rm;r)if(dp[l][r]limit){intcurLenpos[r]-pos[l]1;// 原串中该子串的实际长度intcurStartpos[l]1;// 起始位置1‑basedif(curLenbestLen||(curLenbestLencurStartbestStart)){bestLencurLen;bestStartcurStart;}}coutCase caseNo: bestLen bestStart\n;}return0;}总结本题的关键在于将非字母字符与字母分离只关心字母序列并记录原位置便于计算原始子串长度和起始位置。使用动态规划预处理所有区间的差异数避免重复计算将判断复杂度降为O(1)O(1)O(1)每个区间。注意差异数的定义对称的两个不同字符贡献222个不同位置而非111这是容易出错的地方。枚举所有合法区间并更新答案同时满足长度优先、起始位置次之的排序要求。该解法在n≤1000n \le 1000n≤1000的情况下非常高效代码简洁易于实现。