CF963D 题解

王熙文 · 2022-06-13 19:05:07 · 题解

题解

（注：文中默认 |s|,n,\sum|m_i| 为一个量级，均表示为 n）

首先考虑如果只有一次询问怎么做。

可以在 s 串中找到这一次询问的串的若干出现位置，排序之后答案即为所有连续 k 个位置组成的字符串的长度。

有一个结论：在这道题当中所有询问出现位置的数量总和为 \mathcal O(n\sqrt{n}) 量级。

证明：考虑使用根号分治的思想。

• 当询问的字符串长度 |m_i| \le \sqrt{n} 时，考虑每一个询问的字符串匹配上的位置一定是 s 的某个前缀的长度为 |m_i| 的后缀。整体来看，一共有 n 个前缀，每个前缀的后缀个数最多为 \sqrt{n} 个（因为 |m_i| \le \sqrt{n}），所以一共匹配上的位置共有 \mathcal O(n\sqrt{n}) 个。

• 当询问的字符串长度 |m_i| > \sqrt{n} 时，因为所有询问的字符串长度总和为 n，所以一共最多会有 \mathcal O(\sqrt{n}) 个这样的串，每个串最差匹配 \mathcal O(n) 次，一共匹配上的位置也只有 \mathcal O(n\sqrt{n}) 个。

那么此时就有了一个根号分治的方法：

• 对于每一个 |m_i| > \sqrt{n} 的查询暴力用哈希匹配求出答案。

• 对于所有 |m_i| \le \sqrt{n} 的字符串构建 ACAM（AC 自动机），因为 |m_i| \le \sqrt{n}，所以树高 \le \sqrt{n}，每一次跳 fail 的时候最多会跳 \mathcal O(\sqrt{n}) 次，暴力跳即可。

但是可以发现这样写太麻烦了，有没有好写的做法呢？

如果我们对所有串都建 ACAM，但是每一次跳 fail 都会恰好更新答案，则时间复杂度就会降为所有询问出现位置的数量总和 \mathcal O(n\sqrt{n})。

考虑在跳 fail 的时候下手脚：我们在建树的时候记录一个 lst 数组，lst_i 表示跳 fail 的时候在向根的路径上第一次遇到需要更新字符串的地方。如果求出来了这个数组，则每一次跳 fail 的时候就不再是 j=fail[j]，而是 j=lst[j] 了。显然这个数组可以在求 fail 的时候就求出来：

• 如果当前指向的 fail 的位置就有字符串，需要更新答案，则 lst_i = fail_i。

• 如果当前指向的 fail 的位置没有字符串，则 lst_i=lst_{fail_i}。

求出来这个 lst 数组后，时间复杂度便降下来了。

具体细节参考代码。

参考代码

// 以下是写代码前写的注释，可以参考
// 考虑单次询问，可以找到查询的字符串在原串的几个位置，排序后答案即为连续的 k 个位置的右-左最小
// 口胡可知，若干次询问的位置数量总和 <=nsqrt(n)，具体方法可以用根号分治的思想证明
// 证明：当查询的字符串长度 <=sqrt(n) 的时候，我们将这些串一起匹配。这些串的位置肯定是原串一个前缀的后缀
// 前缀的个数有 n 个，后缀的个数有 O(sqrt(n)) 个，又因为每个串互不相同，所以最差把前缀的 O(sqrt(n)) 个后缀匹配满，共有 O(nsqrt(n)) 个
// 当查询的字符串长度 >sqrt(n) 的时候，通过查询的字符串长度总和可知这样的字符串 <=sqrt(n) 个，暴力对于每个串哈希或者 KMP 即可
// 于是可以使用根号分治做，<=sqrt(n) 的建 ACAM，>sqrt(n) 的暴力
// 但是如果能快速找到答案，就不需要根号分治（因为答案总数已经证明了最多 O(nsqrt(n)) 个
// 考虑对所有查询的字符串建 ACAM，记录 lst 表示对于每一个节点 fail 向根的路径上上一次有字符串的地方的位置，可以在建 fail 边的时候求出
// 那么每一次跳就都能找到需要更新答案的地方，即可 O(nsqrt(n)) 完成
#include<bits/stdc++.h>
using namespace std;

int m;

string s;

struct query
{
    string t;
    int k;
} q[100010];

int now=0,son[100010][26],fail[100010],lst[100010],qwz[100010]; // qwz[i] 表示当前位置是哪个查询的字符串（如果没有，=0）

void insert(string t,int id)
{
    int wz=0;
    for(int i=0; i<t.size(); ++i)
    {
        if(!son[wz][t[i]-'a']) son[wz][t[i]-'a']=++now;
        wz=son[wz][t[i]-'a'];
    }
    qwz[wz]=id;
}

queue<int> qq;

void get_fail()
{
    for(int i=0; i<26; ++i)
    {
        if(son[0][i])
        {
            qq.push(son[0][i]);
            fail[son[0][i]]=0;
        }
    }
    while(!qq.empty())
    {
        int frn=qq.front(); qq.pop();
        for(int i=0; i<26; ++i)
        {
            int now=son[frn][i];
            if(now)
            {
                qq.push(now);
                fail[now]=son[fail[frn]][i];
                lst[now]=qwz[fail[now]]?fail[now]:lst[fail[now]]; // 这里是求 lst 的地方，如果 qwz[fail[now]]!=0 说明那里需要更新 vector
            }
            else son[frn][i]=son[fail[frn]][i];
        }
    }
}

vector<int> twz[100010]; // 记录每个查询的匹配位置右端点

int main()
{
    cin>>s;
    cin>>m;
    for(int i=1; i<=m; ++i)
    {
        cin>>q[i].k>>q[i].t;
        insert(q[i].t,i);
    }
    get_fail();
    int wz=0;
    for(int i=0; i<s.size(); ++i)
    {
        wz=son[wz][s[i]-'a'];
        for(int j=wz; j; j=lst[j])
        {
            if(qwz[j]) twz[qwz[j]].push_back(i);
        }
    }
    for(int i=1; i<=m; ++i)
    {
        int ans=1e9;
        for(int j=0; j<(int)twz[i].size()-q[i].k+1; ++j)
        {
            ans=min(ans,twz[i][j+q[i].k-1]-twz[i][j]+(int)q[i].t.size());
        }
        cout<<(ans==1e9?-1:ans)<<'\n';
    }
    return 0;
}