题意

要求将一个字符串

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

时，处理方法如下：

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

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

代码

CPP

#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:;
        }
    }
}

题解：P11999 投入严厉地本地

文章操作

题意

题解

代码

相关推荐

评论

题解：P11999 投入严厉地本地