洛谷P4022[CTSC2012]熟悉的文章广义后缀自动机+d

题目大意&＃xff1a;
有多个主串&＃xff0c;每次询问将询问串分成多个连续子串&＃xff0c;如果一个子串长度$\ge L$且在主串中出现过就是合法的
如果合法的子串总长度$\ge$询问串长的$90\%$&＃xff0c;这个串就是合法的字符串&＃xff0c;求使得询问串成为合法的字符串的最大的$L$。

分析&＃xff1a;
我们可以二分答案&＃xff0c;显然答案越大可以使用的合法串就越多&＃xff0c;而且是包含关系&＃xff0c;满足二分性。
我们把这些串建一个广义后缀自动机。
设$f[i]$前$i$个位置最多可以覆盖多少个位置。
显然有
$$f[i]\&＃61;max(f[i-1],f[j]\&＃43;i-j)j\in [i-maxc,i-midlen]$$
其中$maxc$是以当前位置结尾的询问串后缀在所有主串中的$lcs$。
这个可以在后缀自动机上跳$fail$。
分三种情况讨论&＃xff0c;如果当前节点有儿子&＃xff0c;直接往儿子走&＃xff0c;maxlen&＃43;1。
如果当前点没有这个儿子&＃xff0c;跳fail到有这个儿子的节点&＃xff0c;显然这个节点代表的串都是可以的&＃xff08;因为后缀自动机每个节点代表不止一个串&＃xff0c;但是都是后缀关系&＃xff09;&＃xff0c;那么显然取最长那个&＃xff0c;即$maxlen\&＃61;t[x].len\&＃43;1$。
如果没有找到儿子&＃xff0c;直接$maxlen\&＃61;0$。

代码&＃xff1a;

#include
#include
#include
#include const int maxn&＃61;3e6&＃43;7;using namespace std;int n,m,cnt,len,head,tail;
int f[maxn],q[maxn];
char s[maxn];struct node{int len,fail;int son[2];
}t[maxn];struct rec{int son[2];
}a[maxn];void ins()
{int now&＃61;1;len&＃61;strlen(s&＃43;1);for (int i&＃61;1;i<&＃61;len;i&＃43;&＃43;){int c&＃61;s[i]-&＃39;0&＃39;;if (!a[now].son[c]) a[now].son[c]&＃61;&＃43;&＃43;cnt;now&＃61;a[now].son[c];}
}int ins_sam(int x,int c)
{int now,p,q,clone;p&＃61;x;if (t[p].son[c]){q&＃61;t[p].son[c];if (t[p].len&＃43;1&＃61;&＃61;t[q].len) return q;clone&＃61;&＃43;&＃43;cnt;t[clone]&＃61;t[q];t[clone].len&＃61;t[p].len&＃43;1;t[q].fail&＃61;clone;while (p&&(t[p].son[c]&＃61;&＃61;q)) t[p].son[c]&＃61;clone,p&＃61;t[p].fail;return clone;}now&＃61;&＃43;&＃43;cnt;t[now].len&＃61;t[p].len&＃43;1;while (p&&(!t[p].son[c])) t[p].son[c]&＃61;now,p&＃61;t[p].fail;if (!p) t[now].fail&＃61;1;else{q&＃61;t[p].son[c];if (t[p].len&＃43;1&＃61;&＃61;t[q].len) t[now].fail&＃61;q;else{clone&＃61;&＃43;&＃43;cnt;t[clone]&＃61;t[q];t[clone].len&＃61;t[p].len&＃43;1;t[now].fail&＃61;t[q].fail&＃61;clone;while (p&&(t[p].son[c]&＃61;&＃61;q)) t[p].son[c]&＃61;clone,p&＃61;t[p].fail;}}return now;
}void dfs(int x,int last)
{int d;if (a[x].son[0]){d&＃61;ins_sam(last,0);dfs(a[x].son[0],d);}if (a[x].son[1]){d&＃61;ins_sam(last,1);dfs(a[x].son[1],d);}
}bool check(int k)
{int p&＃61;1,maxlen&＃61;0;f[0]&＃61;0;head&＃61;1,tail&＃61;0; for (int i&＃61;1;i<&＃61;len;i&＃43;&＃43;){int c&＃61;s[i]-&＃39;0&＃39;;if (t[p].son[c]) maxlen&＃43;&＃43;,p&＃61;t[p].son[c];else{while (p&&(!t[p].son[c])) p&＃61;t[p].fail;if (!p) p&＃61;1,maxlen&＃61;0;else{maxlen&＃61;t[p].len&＃43;1;p&＃61;t[p].son[c];}}f[i]&＃61;f[i-1];if (i-k>&＃61;0) q[&＃43;&＃43;tail]&＃61;i-k;while ((head&＃61;f[q[tail-1]]-q[tail-1])) q[tail-1]&＃61;q[tail],tail--;if (maxlen>&＃61;k){ while (q[head]&＃61;len*9;
}int main()
{scanf("%d%d",&m,&n);cnt&＃61;1; for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%s",s&＃43;1);ins();} cnt&＃61;1; dfs(1,1);for (int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%s",s&＃43;1); len&＃61;strlen(s&＃43;1); int l&＃61;1,r&＃61;len,ans&＃61;0;while (l<&＃61;r){int mid&＃61;(l&＃43;r)/2;if (check(mid)) l&＃61;mid&＃43;1,ans&＃61;mid;else r&＃61;mid-1;}printf("%d\n",ans);}
}