专业的网站制作团队,网站建设的基本步骤是哪些,网站做几级等保,百度做任务的网站差分之后就是求多串LCS。 对其中一个串建SAM#xff0c;然后把其它串放在上面跑。 对SAM上的每个状态都用f[x]记录这个状态与当前串的最长匹配长度#xff0c;res[x]是对每次的f[x]取最小值。答案就是res[]的最大值。 考虑f[x]的求法#xff0c;把s[]放在SAM上跑时#xff…差分之后就是求多串LCS。 对其中一个串建SAM然后把其它串放在上面跑。 对SAM上的每个状态都用f[x]记录这个状态与当前串的最长匹配长度res[x]是对每次的f[x]取最小值。答案就是res[]的最大值。 考虑f[x]的求法把s[]放在SAM上跑时若下一个能正常匹配即son[x][c]!0则直接len否则用经典的跳父亲找到第一个son[k][c]!0的点klenmx[k]1xson[k][c]。每次更新最终匹配到的状态的f[]。同时注意到出现次数可以向父亲传递于是Radixsort之后经典DP转移最长长度即可。 1 #includemap2 #includecstdio3 #includecstring4 #includealgorithm5 #define rep(i,l,r) for (int i(l); i(r); i)6 typedef long long ll;7 using namespace std;8 9 const int N500010;
10 int n,m,x,len,fir,lst1,cnt1,ans,res[N],s[N],f[N],mx[N],fa[N],c[N],q[N];
11 mapint,intson[N];
12
13 void ext(int c){
14 int plst,nplstcnt; mx[np]mx[p]1;
15 while (p !son[p][c]) son[p][c]np,pfa[p];
16 if (!p) fa[np]1;
17 else{
18 int qson[p][c];
19 if (mx[q]mx[p]1) fa[np]q;
20 else{
21 int nqcnt; mx[nq]mx[p]1; son[nq]son[q];
22 while (p son[p][c]q) son[p][c]nq,pfa[p];
23 fa[nq]fa[q]; fa[q]fa[np]nq;
24 }
25 }
26 }
27
28 void Radix(){
29 rep(i,1,cnt) c[mx[i]];
30 rep(i,1,cnt) c[i]c[i-1];
31 for (int icnt; i; i--) q[c[mx[i]]--]i;
32 rep(i,1,cnt) res[i]mx[i];
33 }
34
35 void Go(int s[],int n){
36 int x1,len0;
37 rep(i,1,n){
38 int cs[i];
39 if (son[x][c]) xson[x][c],f[x]max(f[x],len);
40 else{
41 while (x !son[x][c]) xfa[x];
42 if (!x) x1,len0; else lenmx[x]1,xson[x][c],f[x]max(f[x],len);
43 }
44 }
45 for (int icnt; i; i--){
46 int xq[i]; res[x]min(res[x],f[x]);
47 if (f[x] fa[x]) f[fa[x]]mx[fa[x]];
48 f[x]0;
49 }
50 }
51
52 int main(){
53 scanf(%d%d%d,n,len,fir);
54 rep(i,1,len-1) scanf(%d,x),s[i]x-fir,firx;
55 len--; rep(i,1,len) ext(s[i]);
56 Radix();
57 rep(i,2,n){
58 scanf(%d%d,len,fir);
59 rep(i,1,len-1) scanf(%d,x),s[i]x-fir,firx;
60 len--; Go(s,len);
61 }
62 rep(i,2,cnt) ansmax(ans,res[i]);
63 printf(%d\n,ans1);
64 return 0;
65 } 转载于:https://www.cnblogs.com/HocRiser/p/9441117.html
