[Solution] CF2196E1 Fuzzy Concatenation (Easy Version)

cherry2010 · 2026-06-05 11:28:34 · 题解

Solution

容易发现，每次贪心找到尽可能长的子串 [l,r] 填入一定是最优的。因此问题转为，每次往 t 中加入一个字符，判断是否存在一个 s 中的子串满足与 t 串至多 1 位不同。

设 f_{i,0/1,j} 表示当前 t 串长度为 i，是否进行过修改操作时，以 j 结尾的子串是否与 t 串至多 1 位不同。有转移式：

显然可以使用 bitset 优化，时间复杂度 O(\frac{nm}{\omega})，可以通过 E1。加入 GCC 优化后可以通过 E2。

Code

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

char BEGIN;
namespace Cherry {
    const int N=1e5+5,M=1e4+5;
    int T,n,m,ans;
    char s[N],t[M];
    bitset<N> st[26],f[2];
    int main() {
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d",&n,&m);
            scanf("%s%s",s+1,t+1);
            for(int i=0;i<26;i++) st[i].reset();
            for(int i=1;i<=n;i++) st[s[i]-'a'][i]=1;
            ans=0;
            for(int i=1;i<=m;) {
                ans++;
                f[0].set();
                while(i<=m) {
                    f[0]<<=1,f[1]<<=1,f[0][n+1]=f[1][n+1]=0;
                    f[1]=(f[1]&st[t[i]-'a'])|f[0];
                    f[0]=f[0]&st[t[i]-'a'];
                    if(!f[1].count()) break;
                    i++;
                }
            }
            printf("%d\n",ans);
        }

        return 0;
    }
}
char END;

int main() {
    clock_t begin=clock();
    Cherry::main();
    clock_t end=clock();
    fprintf(stderr,"Time: %.3lf/Limit s\n",(end-begin)/1000.0);
    fprintf(stderr,"Memory: %.3lf/Limit MB\n",abs(&BEGIN-&END)/1024.0/1024.0);

    return 0;
}