题解：P11999 投入严厉地本地

· · 题解

题意

要求将一个字符串 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:;
        }
    }
}