CF963D Frequency of String

Frequency of String

莪怺逺禧歡仳特噻特。

记每次询问中的字符串为 \(t_i\)。约定字符串下标从 \(1\) 开始。

发现 \(\sum |t_i|\) 与 \(|s|\) 和 \(q\) 同阶，考虑使用 bitset 进行字符串匹配。

我们对于每一种字符 \(c\) 开一个 bitset \(b_c\)，然后预处理将 \(b_{s_i}\) 的第 \(i\) 位设置为 \(1\)，也就是对于每种字符记录出它在 \(s\) 中所有的出现位置。

对于一个字符串 \(t\)，与 \(s\) 进行字符串匹配。我们开一个记录答案的 bitset \(ans\)，意义是每一个为 \(1\) 的位都是 \(t\) 在 \(s\) 中的起始位置(有些写法是结束位置)。初始时将 \(ans\) 每一位都赋值为 \(1\)。

\(s:abcdabacd\)

\(t:abcd\)

\(ans:1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\)

我们遍历 \(t\) 的每一位，使 \(ans\gets ans\operatorname{bitand} (b_{y_i}\operatorname{>>}(i-1))\)（字符串向左移，但是 bitset 中是右移）。

\(s:\ \ \ \ {\color{red} a}\ b\ c\ d\ {\color{red} a}\ b\ {\color{red} a}\ c\ d\)

\(ans:1\ 0\ 0\ 0\ 1\ 0\ 1\ 0\ 0\)

\(s:\ \ \ \ {\color{red} b}\ c\ d\ a\ {\color{red} b}\ a\ c\ d\)

\(ans:1\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\)

$\cdots $

最后得到的就是所有起始位置，匹配的时间复杂度是 \(O(\dfrac{|s|\sum |t_i|}{\omega})\)。

考虑怎样快速统计答案，直接遍历显然单次 \(O(|s|)\)，可以通过 bitset 的函数 _Find_first() 和 _Find_next(x) 找到 bitset 中第一个为 \(1\) 的位置和 \(x\) 之后第一个为 \(1\) 的位置。就可以直接遍历所有为 \(1\) 的位置。直接统计就可以了。

为什么这样的时间复杂度是正确的，因为 \(t_i\) 互不相同，所以所有 \(t_i\) 在 \(s\) 中总出现次数不超过 \(|s|\sqrt{\sum |t_i|}\)。所以这里时间复杂度是 \(O(|s|\sqrt{\sum |t_i|})\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
using namespace std;
const int MAXN=1e5+10;
string s,t;int n,q,k,ANS;
bitset <MAXN> b[300],ans;
int main()
{
#ifdef ONLINE_JUDGE
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>s>>q;n=s.size();s=' '+s;
    for(register int i=1;i<=n;++i) b[s[i]].set(i);
    for(register int i=1;i<=q;++i)
    {
        cin>>k>>t;ans.set(),ANS=MAXN;
        for(register int i=0;i<t.size();++i) ans&=b[t[i]]>>i;
        int l=ans._Find_first(),r=l;
        for(register int i=1;r<=n&&i<k;++i) r=ans._Find_next(r);
        while(r<=n)
        {
            ANS=min(ANS,r+(int)t.size()-l);
            l=ans._Find_next(l),r=ans._Find_next(r);
        }
        cout<<(ANS==MAXN?-1:ANS)<<'\n';
    }
    return 0;
}