$cheat/$熟悉的文章

2024-03-05 20:42:01

题目描述

阿米巴是小强的好朋友。

在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是
某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文 “熟悉程度”的量化指标：$L_0$ .小强首先将作文转化成一个 $01$ 串。之后，小强搜集了各路名家的文章，同样分别转化成 $01$ 串后，整理出一个包含了 $M$ 个 $01$ 串的“ 标准作文库 ”。

小强认为：如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过（即，它是标准作文库的某个串的一个连续子串），那么它是“ 熟悉 ”的。对于一篇作文（一个 $01$ 串）$A$，如果能够把 $A$ 分割成若干段子串，其中“ 熟悉 ” 的子串的长度总和不少于 $A$ 总长度的 $90\%$，那么称 $A$ 是 “ 熟悉的文章 ”。 $L_0$ 是能够让 $A $成为 “ 熟悉的文章 ” 的所有 $L$ 的最大值（如果不存在这样的 $L$，那么规定 $L_0=0$）

被$SAM$和$dp$爆切就很难受

首先我们发现这个$L$显然有单调性，考虑二分

设 $dp_i$ 表示匹配到第 $i$ 位的最大匹配长度,然后处理 $len_i$ 表示第 $i$ 位能匹配到的最长子串

然后可以设计状态转移方程

首先很显然的 $dp_i=dp_{i-1}$

然后考虑其他转移 $dp_i=\min\limits_{i-len_i \le j\le i-mid}dp_j+i-j$

这个 $dp$ 是 $O(n^2)$ 的，考虑优化

发现可选区间右端点单调，且每个 $dp$ 之间的优劣不会改变,可以用单调队列优化

复杂度$O(\sum|T|log|T|)$

AC代码


#include
#define ll long long
#define cri const register int
#define re register
#define len(tt) t[tt].len
#define c(xx,yy) t[xx].ch[yy]
#define f(xx) t[xx].f
using namespace std;
struct node{
    int ch[3],f,len;
}t[2200010];
int tot=1,rt,las,L[1200010],dp[1200010];
inline void add(cri x){
    int p=las,np=las=++tot;
    len(np)=len(p)+1;
    for(;p&&!c(p,x);p=f(p)) c(p,x)=np;
    if(!p) f(np)=rt;
    else{
        int q=c(p,x);
        if(len(q)==len(p)+1) f(np)=q;
        else {
            int nq=++tot;t[nq]=t[q];
            len(nq)=len(p)+1;
            f(np)=f(q)=nq;
            for(;p&&c(p,x)==q;p=f(p)) c(p,x)=nq;
        }
    }
}
int LEN,que[1100010],n;
char s[1100010];
inline void match(){
    int len=0,now=rt;
    for(int i=1;i<=LEN;i++){
        int in=s[i]-'0';
        if(c(now,in)) now=c(now,in),len++;
        else{
            for(;now&&!c(now,in);now=f(now));
            if(!now) now=rt,len=0;
            else len=len(now)+1,now=c(now,in);
        }
        L[i]=len;
    }
}
inline bool check(cri mid){
    int now=rt,l=1,r=0;
    for(int i=1;i=0.9L*LEN;
}
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
        rt=las=1;
        scanf("%s",s+1);LEN=strlen(s+1);
        for(int j=1;j<=LEN;j++) add(s[j]-'0');
        add(2);
    }
    for(int i=1;i<=N;i++){
        scanf("%s",s+1);LEN=strlen(s+1);
        match();
        int l=0,r=LEN;
        while(l>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        printf("%d\n",l);
    }
}
){>;i++)>

码农公寓

相关文章