莪怺逺禧歡仳特噻特。
记每次询问中的字符串为 \(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;
}