题目描述
输入
第一行两个整数N，M表示待检查的作文数量，和小强的标准作文库的行数
接下来M行的01串，表示标准作文库接下来N行的01串，表示N篇作文输出
N行，每行一个整数，表示这篇作文的Lo 值。
样例输入
1 2 10110 000001110 1011001100
样例输出
4
题解
广义后缀自动机+二分+单调队列优化dp
先建立广义后缀自动机，然后处理出“每篇作文”中的每个字符最多可以向前匹配多少个字符。
这个方法在 中讲过。
对于一个字符，若当前位置存在对应的next指针，则最大匹配长度++，并将当前位置移至对于指针。否则不断在parent树上查找，直到存在next指针，那么最大匹配长度为此位置的dis值+1，并将当前位置赋为此位置的next指针；如果找不到next指针，则最大匹配长度为0，将当前位置赋为root。
处理出最大匹配长度后，考虑怎样求答案。
显然答案是可以二分的，所以我们二分答案，然后求出该L值=mid下的最大“熟悉”长度。
设f[i]表示前i个字符的最大“熟悉”长度，mx[i]为第i个字符的最大匹配长度，那么有状态转移方程$f[i]=f[i-1]\ ,\ f[i]=f[j]+i-j\ (i-mx[i]\le j\le i-mid)$。
那么我们用单调队列维护f[j]-j的最大值即可再$O(n)$时间内求出f[n]，最后判断f[n]/n是否≥0.9即可。这里有精度问题，所以需要把除法转化为乘法来求。
根据二分结果调整边界即可得到答案。
#include#include #include #define N 1100010using namespace std;int next[N << 1][2] , fa[N << 1] , dis[N << 1] , last , tot = 1 , n , mx[N] , f[N] , q[N];char str[N];void ins(int c){ int p = last , np = last = ++tot; dis[np] = dis[p] + 1; while(p && !next[p][c]) next[p][c] = np , p = fa[p]; if(!p) fa[np] = 1; else { int q = next[p][c]; if(dis[q] == dis[p] + 1) fa[np] = q; else { int nq = ++tot; memcpy(next[nq] , next[q] , sizeof(next[q])) , dis[nq] = dis[p] + 1 , fa[nq] = fa[q] , fa[np] = fa[q] = nq; while(p && next[p][c] == q) next[p][c] = nq , p = fa[p]; } }}bool judge(int mid){ int i , l = 1 , r = 0; for(i = 1 ; i <= n ; i ++ ) f[i] = 0; for(i = mid ; i <= n ; i ++ ) { f[i] = f[i - 1]; while(l <= r && f[q[r]] - q[r] < f[i - mid] - i + mid) r -- ; q[++r] = i - mid; while(l <= r && q[l] < i - mx[i]) l ++ ; if(l <= r) f[i] = max(f[i] , f[q[l]] - q[l] + i); } return f[n] * 10 >= n * 9;}int main(){ int T , m , i , j , len , p , l , r , mid , ans; scanf("%d%d" , &T , &m); for(i = 1 ; i <= m ; i ++ ) { scanf("%s" , str + 1) , len = strlen(str + 1) , last = 1; for(j = 1 ; j <= len ; j ++ ) ins(str[j] - '0'); } while(T -- ) { scanf("%s" , str + 1) , n = strlen(str + 1); for(p = i = 1 , len = 0 ; i <= n ; i ++ ) { if(next[p][str[i] - '0']) len ++ , p = next[p][str[i] - '0']; else { while(p && !next[p][str[i] - '0']) p = fa[p]; if(p) len = dis[p] + 1 , p = next[p][str[i] - '0']; else len = 0 , p = 1; } mx[i] = len; } l = 1 , r = n , ans = 0; while(l <= r) { mid = (l + r) >> 1; if(judge(mid)) ans = mid , l = mid + 1; else r = mid - 1; } printf("%d\n" , ans); } return 0;}