题目概述

Beautiful Words

解题报告

先把 $A$ 复制一份，令 $B_i=A[i-n+1,i]$ 。

然后二分答案 $mid$ ，这样就只需要验证是否存在 $i\in[n,2n-1]$ 使得 $B_i$ 中不存在长度 $>mid$ 的 $S$ 中字符串的子串。

接下来考虑二分验证，如果 $A[i-len+1,i]$ 是 $S_k$ 的一个子串，说明 $j\in[i,i-len+n]$ 的 $B_j$ 都存在长度为 $len$ 的 $S$ 中字符串的子串。可以发现 $len$ 越小，区间 $[i,i-len+n]$ 越长，因此我们只需要考虑 $len=mid+1$ 的情况，然后考虑所有 $B$ 的违法区间 $[i,i-(mid+1)+n]$ 是否覆盖了 $[n,2n-1]$ ，如果没有覆盖说明存在一个合法位置。

因此，如果我们能求出 $suf_i$ 表示 $A$ 以 $i$ 结尾往前能匹配的最长长度，就可以知道 $i$ 位置是否存在 $>mid$ 的子串。

不难想到对 $S$ 中的字符串建广义后缀自动机，然后将 $A$ 放到自动机上匹配就可以求出 $suf_i$ 。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000;

int n,m;char s[maxn+5],t[maxn+5];
int pl=1,ro=1,son[maxn+5][26],fai[maxn+5],MAX[maxn+5];
int suf[maxn+5],c[maxn+5];

int Extend(int p,int c){
    if (son[p][c]){
        int q=son[p][c];if (MAX[p]+1==MAX[q]) return q;
        int nq=++pl;MAX[nq]=MAX[p]+1;for (int i=0;i<26;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=nq;while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return nq;
    } else {
        int np=++pl;MAX[np]=MAX[p]+1;
        while (p && !son[p][c]) son[p][c]=np,p=fai[p];
        if (!p) {fai[np]=ro;return np;}
        int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
        int nq=++pl;MAX[nq]=MAX[p]+1;for (int i=0;i<26;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=fai[np]=nq;while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return np;
    }
}
bool check(int mid){
    for (int i=0;i<(n<<1);i++) c[i]=0;
    for (int i=1;i<(n<<1);i++)
        if (suf[i]>mid){
            int L=i,R=min(i-(mid+1)+n,(n<<1)-1);
            c[L]++;c[R+1]--;
        }
    for (int i=1;i<(n<<1);i++) c[i]+=c[i-1];
    for (int i=n;i<(n<<1);i++) if (!c[i]) return true;
    return false;
}
int main(){
    scanf("%d%d%s",&n,&m,s+1);
    for (int i=1;i<n;i++) s[i+n]=s[i];
    for (int i=1;i<=m;i++){
        scanf("%s",t+1);
        for (int j=1,p=ro;t[j];j++) p=Extend(p,t[j]-'a');
    }
    for (int i=1,p=ro,len=0;i<(n<<1);i++){
        while (p && !son[p][s[i]-'a']) p=fai[p],len=MAX[p];
        if (p) p=son[p][s[i]-'a'],len++; else p=ro,len=0;
        suf[i]=min(i,min(len,n));
    }
    int L=0,R=n;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        check(mid)?R=mid-1:L=mid+1;
    printf("%d\n",L);
    return 0;
}