题解 [CF954I] Yet Another String Matching Problem

· · 题解

题目描述

给定两个字符串 S, T, len_S \ge len_T, 字符集大小为 [a, f]。

每次操作可以将一种字符变成另外一种字符，对于 S 的每一个位置，询问最少进行多少次操作，可以变成 T。

正解

可以暴力枚举集合划分（即哪些字符要变成相同的），然后用哈希或者 KMP 做到 O(n) 判断是否可行。

之前有些题解说的复杂度不太对，集合划分的复杂度是 O(Bell(n)) 的而不是 O(n!) 的，而 B_6 只有 203，所以足矣通过此题。

讲一下怎么搜集合划分吧。

其实集合划分的写法就跟生成森林的方法差不多。

从小往大枚举元素，对于一个元素，它有两种操作 :

  1. 作为新的森林的根。

  2. 加入一个已经存在的森林。

给出代码 :

int fa[N];
int blk[N], cb;

void divSet(int dep) {
    if(dep > maxDep) {
        solve();
        return void();
    }

    fa[dep] = dep;
    blk[++cb] = dep;
    divSet(dep + 1);

    blk[cb--] = 0;
    for(int i = 1; i <= cb; ++i) {
        fa[dep] = blk[i];
        divSet(dep + 1);
    }
}

话说这题 O(Bell(|\Sigma|)\times n) 的复杂度其实可以跑 |\Sigma| = 8，但 |\Sigma| 更大的情况就不能这么做了。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 125005;

int ans[N];
int fail[N];
int lenS, lenT;
char s[N], t[N];

int fa[N];
int blk[N], cb;

inline int tr(char ch) { return ch - 'a'; }

void solve(int res) {
    int cur(0);
    fail[1] = 0;
    for(int i = 2; i <= lenT; ++i) {
        while(cur && fa[tr(t[i])] != fa[tr(t[cur + 1])])
            cur = fail[cur];
        if(fa[tr(t[i])] == fa[tr(t[cur + 1])])
            ++cur;
        fail[i] = cur;
    }
    cur = 0;
    for(int i = 1; i <= lenS; ++i) {
        while(cur && fa[tr(s[i])] != fa[tr(t[cur + 1])])
            cur = fail[cur];
        if(fa[tr(s[i])] == fa[tr(t[cur + 1])])
            ++cur;
        if(cur == lenT) {
            ans[i] = min(ans[i], res);
            cur = fail[cur];
        }
    }
}

void divSet(int dep) {
    if(dep > tr('f')) {
        ++cnt;
        solve(6 - cb);
        return void();
    }

    fa[dep] = dep;
    blk[++cb] = dep;
    divSet(dep + 1);

    blk[cb--] = 0;
    for(int i = 1; i <= cb; ++i) {
        fa[dep] = blk[i];
        divSet(dep + 1);
    }
}

int main() {
    scanf("%s %s", s + 1, t + 1);
    lenS = strlen(s + 1);
    lenT = strlen(t + 1);

    for(int i =lenT; i <= lenS; ++i)
        ans[i] = 233;
    divSet(0);
    for(int i = lenT; i <= lenS; ++i)
        printf("%d%c", ans[i], " \n"[i == lenS]);
    return 0;
}