题解

题意分析

题目要求找到最短的小写字母字符串$x$，使得：

• 将$x$分别附加到字符串$a$和$b$后
• 两个结果字符串$ax$和$bx$中恰好有一个是回文串
• 若存在多个解，选择字典序最小的
• 若无解则输出"无解"

解题思路

1. 回文判断：实现辅助函数判断字符串是否为回文
2. 枚举策略：从小到大枚举可能的$x$长度（$0$到$2000$）
3. 字典序生成：对于每个长度，按字典序生成所有可能的$x$
4. 条件检查：对每个$x$，检查$ax$和$bx$是否满足恰好一个回文的条件
5. 提前终止：找到满足条件的最短$x$后立即返回

实现步骤

1. 输入处理：读取多组输入的字符串$a$和$b$
2. 回文判断：实现$is\_palindrome$函数
3. 枚举长度：从$0$开始枚举可能的$x$长度
4. 生成$x$：对每个长度按字典序生成所有可能的$x$
5. 条件验证：检查$ax$和$bx$的回文状态
6. 结果输出：返回第一个满足条件的$x$，或无解提示

代码注释

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 判断字符串是否为回文
bool is_palindrome(const string& s) {
    string reversed = s;
    reverse(reversed.begin(), reversed.end()); // 反转字符串
    return s == reversed; // 比较原串和反转串
}

// 查找满足条件的最短x
string find_shortest_x(const string& a, const string& b) {
    // 枚举x的可能长度(0到2000)
    for (int len = 0; len <= 2000; ++len) {
        string x(len, 'a'); // 初始化为全'a'
        bool done = false;
        
        while (true) {
            string ax = a + x; // 构造ax
            string bx = b + x; // 构造bx
            
            bool ax_pal = is_palindrome(ax); // 判断ax是否为回文
            bool bx_pal = is_palindrome(bx); // 判断bx是否为回文
            
            // 检查是否恰好一个回文
            if ((ax_pal && !bx_pal) || (!ax_pal && bx_pal)) {
                return x; // 返回当前x
            }
            
            // 生成字典序下一个x
            int i = len - 1;
            while (i >= 0 && x[i] == 'z') { // 处理进位
                x[i] = 'a';
                --i;
            }
            
            if (i < 0) { // 所有组合已尝试
                done = true;
                break;
            }
            ++x[i]; // 递增当前位
        }
        
        if (done) break; // 当前长度无解，尝试更长x
    }
    return "No Solution."; // 无解
}

int main() {
    string a, b;
    while (cin >> a >> b) { // 读取多组输入
        cout << find_shortest_x(a, b) << endl; // 输出结果
    }
    return 0;
}

复杂度分析

• 时间复杂度：最坏情况下为$O(26^L \cdot (N+M))$，其中$L$是$x$的最大长度，$N$和$M$是$a$和$b$的长度
• 空间复杂度：$O(N+M+L)$，主要用于存储字符串和中间结果