当前位置：首页 > news >正文

UVa 10262 Suffidromes

news 2026/5/11 22:39:25

题目描述

给定两个小写字母字符串aaa和bbb，要求构造一个最短的小写字母字符串xxx，使得axaxax和bxbxbx这两个拼接字符串中恰好有一个是回文串（即反转后与自身相等），另一个不是。

输入格式

标准输入包含多组数据，每组数据包含两行，每行一个字符串。字符串由小写字母组成，长度在000到100010001000之间。

输出格式

对于每组数据，输出一行答案字符串xxx。如果存在多个满足条件的xxx，选择长度最短且字典序最小的那个。如果不存在这样的xxx，输出No solution.。

样例输入

abab ababab abc def

样例输出

baba ba

题目分析

本题要求构造一个字符串xxx，使得a+xa+xa+x和b+xb+xb+x中恰好一个是回文串。我们需要找到最短且字典序最小的解。

问题特点

回文性质：如果s+xs+xs+x是回文串，那么它的反转等于自身：reverse(s+x)=s+xreverse(s+x) = s+xreverse(s+x)=s+x。
结构约束：设rev(s)rev(s)rev(s)表示sss的反转。若s+xs+xs+x是回文，则有：
s+x=reverse(s+x)=reverse(x)+rev(s) s + x = reverse(s+x) = reverse(x) + rev(s)s+x=reverse(s+x)=reverse(x)+rev(s)
这意味着xxx必须与rev(s)rev(s)rev(s)的某个后缀匹配。

关键观察

经过推导，我们可以得到一个重要结论：
如果s+xs+xs+x是回文串，那么xxx一定是rev(s)rev(s)rev(s)的某个后缀，且该后缀对应的前缀是回文串。

证明：
设n=∣s∣n = |s|n=∣s∣，m=∣x∣m = |x|m=∣x∣。
由于s+xs+xs+x是回文，其长度为n+mn+mn+m。考虑字符串的后mmm个字符，即xxx。
因为回文对称性，xxx必须等于rev(s)rev(s)rev(s)的前mmm个字符。
同时，为了保证整个字符串是回文，rev(s)rev(s)rev(s)的前mmm个字符（即xxx的反转）必须与sss的后mmm个字符匹配。
更形式化地，可以证明：xxx是rev(s)rev(s)rev(s)的后缀，且rev(s)rev(s)rev(s)去掉这个后缀后剩下的前缀是回文串。

解题思路

基于上述观察，我们可以设计如下算法：

1. 特判

如果a=ba = ba=b，那么对于任意xxx，a+xa+xa+x和b+xb+xb+x总是同时为回文或同时不为回文，因此不存在解，直接输出No solution.。

2. 构造候选解

对于每个字符串sss（aaa或bbb），我们构造所有可能的xxx，使得s+xs+xs+x是回文串。方法如下：

计算rev=reverse(s)rev = reverse(s)rev=reverse(s)。
枚举分割点iii（从−1-1−1到n−1n-1n−1，其中n=∣rev∣n = |rev|n=∣rev∣）：
- 取prefix=rev[0…i]prefix = rev[0 \dots i]prefix=rev[0…i]（当i=−1i=-1i=−1时为空串）
- 如果prefixprefixprefix是回文串，则x=rev[i+1…n−1]x = rev[i+1 \dots n-1]x=rev[i+1…n−1]是一个候选解
额外考虑一种情况：在revrevrev前面添加一个字符ccc（ccc从'a'到'z'），得到c+revc + revc+rev作为候选解。这对应了xxx比revrevrev长一个字符的情况。

3. 合并与筛选

分别计算aaa和bbb的候选解集合AAA和BBB。
合并两个集合，去重并按照长度优先、字典序次优先排序。
遍历排序后的候选解，检查每个xxx是否满足条件（a+xa+xa+x和b+xb+xb+x恰好一个是回文）。
输出第一个满足条件的xxx。

4. 复杂度分析

回文判断：O(n)O(n)O(n)，其中nnn是字符串长度。
构造候选解：枚举O(n)O(n)O(n)个分割点，每个点做一次O(n)O(n)O(n)的回文检查，共O(n2)O(n^2)O(n2)。
候选解数量：O(n)O(n)O(n)个。
排序：O(nlog⁡n)O(n \log n)O(nlogn)。
总复杂度：O(n2)O(n^2)O(n2)，对于n≤1000n \leq 1000n≤1000完全可行。

5. 正确性证明

算法的正确性基于上述数学推导：我们枚举了所有可能使s+xs+xs+x成为回文的xxx。因此，如果存在解，它一定在候选解集合中。我们按长度和字典序排序后遍历，找到的第一个满足“恰好一个回文”条件的解就是题目要求的最优解。

代码实现

// Suffidromes// UVa ID: 10262// Verdict: Accepted// Submission Date: 2025-12-24// UVa Run Time: 0.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;boolcmp(string a,string b){if(a.size()!=b.size())returna.size()<b.size();returna<b;}// 判断回文boolisPalindrome(conststring&s){intleft=0,right=s.size()-1;while(left<right)if(s[left++]!=s[right--])returnfalse;returntrue;}// 获取所有可能的 x，使得 s+x 是回文vector<string>getCandidates(conststring&s){vector<string>result;string ss=s;reverse(ss.begin(),ss.end());intn=ss.size();// 枚举分割点 i，如果 reversed[0..i] 是回文，那么可以取 reversed[i+1,n-1] 作为 xfor(inti=-1;i<n;++i){string x=ss.substr(0,i+1);if(isPalindrome(x))result.push_back(ss.substr(i+1));}// 增加一个字符，构成长度为奇数的回文for(chari='a';i<='z';i++)result.push_back(i+ss);returnresult;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string a,b;while(getline(cin,a)){getline(cin,b);// 两个字符串相等则不存在解if(a==b){cout<<"No solution.\n";continue;}if(a.size()>b.size())swap(a,b);vector<string>A=getCandidates(a),B=getCandidates(b);for(autos:B)A.push_back(s);sort(A.begin(),A.end(),cmp);A.erase(unique(A.begin(),A.end()));for(autos:A)if(isPalindrome(a+s)&&!isPalindrome(b+s)||!isPalindrome(a+s)&&isPalindrome(b+s)){cout<<s<<'\n';break;}}return0;}