CF 954I Yet Another String Matching Problem

题目描述

https://codeforces.com/problemset/problem/954/I

简要题意：给定两个字符串 $S$ 和 $T$，定义两个长度相同的字符串的距离为需要多少次操作可以将两个字符串变得完全相同，每次操作可以选择两个字符 $c_1, c_2$ 将两个字符串中所有 $c_1$ 变成 $c_2$，求 $S$ 的所有长度为 $|T|$ 的字符串与 $T$ 的距离

$|S|,|T|\le 125000,\sum =6$

Solution

我们直接 $dfs$ 枚举字符的集合划分，然后 $kmp$ 即可，时间复杂度 $O(B_6n)$，$B_6=203$

#include <iostream>
#include <cstring>
#define maxn 125010
using namespace std;

int n, m; 
char s[maxn], t[maxn], ss[maxn], tt[maxn];

int nxt[maxn], ans[maxn];
void init_nxt(char *s) {
    int k = 0, l = strlen(s + 1); nxt[1] = 0; 
    for (int i = 2; i <= l; ++i) {
        while (k && s[k + 1] != s[i]) k = nxt[k];
        if (s[k + 1] == s[i]) ++k;
        nxt[i] = k;
    }
}
void kmp(char *s, char *t, int res) {
    int k = 0, l1 = strlen(s + 1), l2 = strlen(t + 1); 
    for (int i = 1; i <= l1; ++i) {
        while (k && s[i] != t[k + 1]) k = nxt[k];
        if (t[k + 1] == s[i]) ++k;
        if (k == l2) ans[i - k + 1] = min(ans[i - k + 1], res); 
    }
}

char tr[256], id[7];
void dfs(int q, int k) {
    if (q == 6) {
        for (int i = 1; i <= n; ++i) ss[i] = tr[s[i]];
        for (int i = 1; i <= m; ++i) tt[i] = tr[t[i]];
        init_nxt(tt); kmp(ss, tt, 6 - k); return ; 
    }
    tr[q + 'a'] = q + 'a', id[k + 1] = q + 'a', dfs(q + 1, k + 1);
    for (int i = 1; i <= k; ++i) tr[q + 'a'] = id[i], dfs(q + 1, k); 
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1 >> t + 1; n = strlen(s + 1); m = strlen(t + 1);
    fill(ans + 1, ans + n - m + 1 + 1, 5), dfs(0, 0);
    for (int i = 1; i <= n - m + 1; ++i) cout << ans[i] << " \n"[i == n - m + 1];
    return 0; 
}