题解：CF2104E Unpleasant Strings

· · 题解

看到 \sum|t_i| \le 1 \times 10^6，看能不能搞出一种 O(\sum|t_i|) 的算法。

我们想到预处理 s 串上每个下标 i 的 ans_i，表示以 i 结尾的子序列最少还要加多少个字符才能不再成为悦耳字符串。

考虑如何预处理。i 从后往前枚举，记录一个 lst_i 表示字符 i 最后出现的地方。我们枚举每个字符。有显然的转移：ans_i = \min\{ans_{lst_i} + 1\}，表示在这个点后面接每个字符的方案。lst 初始全为 n + 1，且 ans_{n + 1} = 0。再记录一个 son_{i,j}，每次都把 lst 给 memcpy 进 son_i。转移完了再更新 lst。最后把 lst memcpy 进 son_0。

考虑如何处理询问。就像字典树一样，我们记录一个 rt 表示当前跳到了 rt 这个点。枚举 t 里每个字符 t_i，每次跳到 son_{rt,t_i}。如果说跳着跳着直接跳到 n + 1 了，就说明它本就不是悦耳字符串，ans 置为 0 并 break。反之如果跳到了 t 的结尾了都没跳出去，就说明这是一个悦耳字符串，答案即为 ans_{rt}。

code:

#include<bits/extc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + 5;
int n,k,q;
char t[maxn],s[maxn];
int son[maxn][26],ans[maxn];
signed main()
{
    scanf("%d%d%s",&n,&k,t + 1);
    fill(son[0],son[0] + k,n + 1);// 这里直接把 son[0] 当 lst 用了
    fill(ans + 1,ans + n + 1,inf);// ans 初始化 inf
    for (int i = n; i >= 1; i--)
    {
        memcpy(son[i],son[0],sizeof(int) * k);// 把 lst memcpy 进 son[i]
        for (int j = 0; j < k; j++)
            ans[i] = min(ans[i],ans[son[0][j]] + 1);// 转移
        son[0][t[i] - 'a'] = i;// 更新 lst
    }
    scanf("%d",&q);
    while (q--)
    {
        scanf("%s",s + 1);
        int rt = 0,len = strlen(s + 1);
        for (int i = 1; i <= len && rt <= n; i++)
            rt = son[rt][s[i] - 'a'];// 每次跳，如果跳出去了就说明本就不是悦耳字符串。
        printf("%d\n",ans[rt]);
    }
    return 0;
}