CF963D Frequency of String 题解

L_G_J · 2022-07-13 14:55:26 · 题解

需要发现一个重要性质：对于 n 个互不相同的模式串 t_i ，他们在文本串 s 中的出现次数之和（即 endpos 大小之和）是 O(|s|\sqrt {\sum |t_i|}) 的。

证明考虑把模式串按长度分类，那么对于长度为 l_i 的一些模式串，他们在 s 中出现的次数之和至多是 |s|-l_i+1 。由于 \sum l_i \leq \sum |t_i| 且 l_i 互不相同，不同的 l_i 至多有 \sqrt{\sum{|t_i|}} 种，所以总的个数是 O(|s|\sqrt {\sum |t_i|})。

所以我们可以对于每个模式串 t_i 维护出它在 s 中的 endpos 集合大小。可以 SAM+线段树合并，这里使用类似于 CF914F 的手法利用 bitset 维护 endpos 集合即可。即对于字符集中的每一个字母用 bitset 维护出它在 s 中的出现位置集合。对于一个模式串，维护一个初始全为 1 的 bitset，依次处理模式串中的字符，通过简单的左移或右移减小这个 bitset 的规模，从而得到最后模式串的所有 endpos，复杂度是 O(\dfrac {|s|\sum |t _i| }{ \omega})。

这样我们获得了一个用 bitset 维护的 endpos 集合，那么直接遍历 bitset 中的每一个 1，对于连续的 k 个 1 代表的区间长度求最小值即可，遍历每个 1 可以使用函数 _Find_first() 以及 _Find_next(x) ，其作用分别为返回 bitset 中的第一个 1 的位置（以数值表示）以及当前的下一个 1 的位置，这样就可以在 O(\dfrac {n |s|}{ \omega}+|s|\sqrt {\sum |t_i|}) 的复杂度内完成统计。

总复杂度 O(\dfrac {|s|(\sum |t _i|+n) }{ \omega} + |s|\sqrt {\sum |t_i|})。

代码

const int N=2e5+50;
int n,m,q,k;
vector<int> vec;
bitset<N> bit[26],cur;
char s[N],t[N];
int main(void)
{
    scanf("%s",s+1),n=strlen(s+1),q=read();
    fr(i,0,25) bit[i].reset();
    fr(i,1,n) bit[s[i]-'a'].flip(i);
    fr(i,1,q)
    {
        k=read(),scanf("%s",t+1),m=strlen(t+1),cur.set(),vec.clear();
        fr(j,1,m) cur&=(bit[t[j]-'a']<<(m-j));
        for(int pos=cur._Find_first();pos!=N;pos=cur._Find_next(pos)) vec.emplace_back(pos);
        int sz=vec.size(),ans=inf;
        fr(j,k-1,sz-1) ans=min(ans,vec[j]-vec[j-k+1]+m);
        (ans==inf)?writeln(-1):writeln(ans); 
    }
    return 0;
}