自动搬运

查看原文

来自洛谷，原作者为

	SnowFlavour 灭六国者 非秦也 六国也

搬运于2025-08-24 23:11:59，当前版本为作者最后更新于2025-03-31 08:45:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

要求将一个字符串 $S$ 的每一个前缀的长度为 $k$ 的后缀替换成一个字符得到 $T$，求可行的映射。

题解

注意到 $|S|$ 和 $|T|$ 都非常小，显然可以用指数或者阶乘复杂度的算法过掉。

于是我们就想到可以枚举映射关系，可是这样有点太麻烦。考虑到很多枚举的状态根本没有用处，比如一个字符串 abcdefg，枚举 iakioi 这样的后缀就根本不可能有用。

因此考虑只关注每一个后缀的映射，还是以 abcdefg 为例，假如 $k = 3$，我们就只用关心 abc，bcd，cde，def，efg 五个字符串即可。

现在考虑如果每一个字符串都映射到一个字符，那么最终的 $T$ 的长度应该和 $S$ 相等。但是 $|T| \le |S|$，因此全都映射到字符不一定可行。

但是题目要求我们可以把某一个后缀替换成空字符，这也就启发我们，只要枚举替换成空字符的后缀即可。具体而言，可以二进制枚举。

那么怎么才能算是可行的方案呢？这里，我们要考虑到本题的映射关系是多对一的，也就是多个后缀可以映射到同一个字符，但是一个后缀只能映射到一个字符。

比如说当 $S$ 为 abab，$T$ 为 ac ，$k=2$ 时，我们可以发现一种可行的映射方式为 $ab \to \epsilon$，$ba \to c$。但是如果我们令 $ab \to c$，那么在后面的时候，由于整个 $T$ 都被扫完了，所以应该有 $ab \to \epsilon$，于是出现了冲突。

因此，我们只需要枚举以后，尝试找到映射就行。一个简单的方法是用 map，当扫描到一个后缀 $x$，此时应该将这个位置映射到 $c$ 时，处理方法如下：

1. 在 map 中没有找到 $x$，直接添加一个映射 $x \to c$。
2. 在 map 中找到 $x$ 并且和 $c$ 相同，继续。
3. 在 map 中找到 $x$，但是和 $c$ 不同，这个方式不行，退出。

注意一个细节：如何区分 map 中的“空字符”和“没有映射关系”？不能直接用\0 作为空字符，因为如果你没有找到映射关系，map 也会返回一个 \0，这样就乱套了。一个简单的方式是利用一个特殊符号（比如 *） 代替空字符。

代码

#include <bitset>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
template <typename T1, typename T2> using umap = unordered_map<T1, T2>;
inline string get(string s, int fr, int to) {
    string tmp = "";
    for (int i = fr; i <= to; i++) tmp.push_back(s[i]);
    return tmp;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        string s, t;
        cin >> s >> t;
        int k, n = s.size(), m = t.size();
        t = t + "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
        cin >> k;
        umap<string, char> mp;
        for (int i = 0; i < (1 << n); i++) {
            if (__builtin_popcount(i >> (k - 1)) != (n - m)) continue;
            // cout << bitset<7>(i) << endl;
            mp.clear();
            int pnt = k;
            for (int j = k; j <= n; j++) {
                string nw = get(s, j - k, j - 1);
                if (i & (1 << (j - 1))) {
                    if (mp[nw] && mp[nw] != '*') goto FAIL;
                    mp[nw] = '*';
                    continue;
                }
                if (mp[nw] && (mp[nw] != t[pnt - 1])) goto FAIL;
                mp[nw] = t[(pnt++) - 1];
            }
            cout << mp.size() << endl;
            for (auto it : mp) {
                if (it.second != '*') cout << "(" << it.first << "," << it.second << ")" << endl;
                else cout << "(" << it.first << "," << ")" << endl;
            }
            break;
        FAIL:;
        }
    }
}