生活随笔
收集整理的這篇文章主要介紹了
[XSY] 最长公共子串对（后缀自动机）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
最長公共子串對
先放一段考場暴力代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std
;
char a
[2005],b
[2005];
int na
,nb
,f
[2005][2005],c
[2005][2005],ans
;
int lowbit(int x
){return x
&(-x
);
}
void update(int x
,int y
,int v
){for(int i
=x
;i
<=na
;i
+=lowbit(i
)){for(int j
=y
;j
<=nb
;j
+=lowbit(j
)){c
[i
][j
]=max(c
[i
][j
],v
);}}
}
int query(int x
,int y
){int res
=0;for(int i
=x
;i
;i
-=lowbit(i
)){for(int j
=y
;j
;j
-=lowbit(j
)){res
=max(res
,c
[i
][j
]);}}return res
;
}
int main(){scanf("%s%s",a
+1,b
+1);na
=strlen(a
+1);nb
=strlen(b
+1);for(int i
=1;i
<=na
;i
++){for(int j
=1;j
<=nb
;j
++){if(a
[i
]==b
[j
]) f
[i
][j
]=max(f
[i
][j
],f
[i
-1][j
-1]+1);ans
=max(ans
,query(i
-f
[i
][j
],j
-f
[i
][j
])+f
[i
][j
]);update(i
,j
,f
[i
][j
]);}}printf("%d\n",ans
);return 0;
}
在這段代碼中，能優(yōu)化的地方有兩個：
1.求最長公共子串(即求fff)可以用SAM，對s串建一個SAM，讓 t 在 s 的SAM上做匹配
（這是一個非常經(jīng)典的問題，但我考試時連SAM是什么都忘了。。。）
2.我拼接兩段公共子串時，用的是二維樹狀數(shù)組，能不能轉(zhuǎn)為一維呢？
答案是可以的。題目的本質(zhì)，其實就是拼接兩段公共子串。
s,t前綴的公共子串是s,t串的公共子串，s,t后綴的公共子串當然也是。
如果我們枚舉i，拼接t[1…i]與s前綴的公共子串和t[i+1…n]與s后綴的公共子串，那么就只需保證 我們所選的兩段公共子串在s串上不相交，這個用一維樹狀數(shù)組即可維護
正序t 在正序s 的SAM上做匹配，可以求s,t前綴的最長公共子串，
那么，逆序t 在逆序s 的SAM上做匹配，即可以求s,t后綴的最長公共子串。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std
;
const int N
=2e5+5;
struct SAM
{int tot
,lst
,ch
[N
<<1][26],len
[N
<<1],fa
[N
<<1],pos
[N
<<1];int tax
[N
<<1],id
[N
<<1];SAM(){tot
=lst
=1;}void add(int c
,int id
){int p
=lst
,np
=lst
=++tot
;len
[np
]=len
[p
]+1;pos
[np
]=id
;for(;p
&&!ch
[p
][c
];p
=fa
[p
])ch
[p
][c
]=np
;if(!p
) fa
[np
]=1;else{int q
=ch
[p
][c
];if(len
[q
]==len
[p
]+1) fa
[np
]=q
;else{int nq
=++tot
;for(int i
=0;i
<26;i
++) ch
[nq
][i
]=ch
[q
][i
];fa
[nq
]=fa
[q
];len
[nq
]=len
[p
]+1;pos
[nq
]=pos
[q
];fa
[q
]=fa
[np
]=nq
;for(;p
&&ch
[p
][c
]==q
;p
=fa
[p
]) ch
[p
][c
]=nq
;}}}void sort(){for(int i
=1;i
<=tot
;i
++) tax
[len
[i
]]++;for(int i
=1;i
<=tot
;i
++) tax
[i
]+=tax
[i
-1];for(int i
=tot
;i
>=1;i
--) id
[tax
[len
[i
]]--]=i
;}
}pre
,suf
;
char s
[N
],t
[N
];
int n
,m
,tag
[N
<<1],ans
;
struct Qry
{int length
,p
;
};
vector
<Qry
> pf
[N
],sf
[N
];
int c
[N
];
int lowbit(int x
){return x
&(-x
);
}
void update(int x
,int v
){for(int i
=x
;i
<=n
;i
+=lowbit(i
)) c
[i
]=max(c
[i
],v
);
}
int query(int x
){int res
=0;for(int i
=x
;i
;i
-=lowbit(i
)) res
=max(res
,c
[i
]);return res
;
}
int main(){scanf("%s%s",s
+1,t
+1);n
=strlen(s
+1);m
=strlen(t
+1);for(int i
=1;i
<=n
;i
++) pre
.add(s
[i
]-'a',i
);for(int i
=n
;i
>=1;i
--) suf
.add(s
[i
]-'a',n
-i
+1);pre
.sort();suf
.sort();for(int i
=1,u
=1,len
=0;i
<=m
;i
++){int c
=t
[i
]-'a';while(u
&&!pre
.ch
[u
][c
]) u
=pre
.fa
[u
];if(!u
){u
=1;len
=0;}else{len
=min(len
,pre
.len
[u
])+1;u
=pre
.ch
[u
][c
];}if(u
>1&&!tag
[pre
.fa
[u
]]) tag
[pre
.fa
[u
]]=i
;pf
[i
].push_back((Qry
){len
,pre
.pos
[u
]});}for(int i
=pre
.tot
;i
>=1;i
--){int u
=pre
.id
[i
];if(!tag
[u
]) continue;if(!tag
[pre
.fa
[u
]]||tag
[pre
.fa
[u
]]>tag
[u
]) tag
[pre
.fa
[u
]]=tag
[u
];pf
[tag
[u
]].push_back((Qry
){pre
.len
[u
],pre
.pos
[u
]});} memset(tag
,0,sizeof(tag
));for(int i
=m
,u
=1,len
=0;i
>=1;i
--){int c
=t
[i
]-'a';while(u
&&!suf
.ch
[u
][c
]) u
=suf
.fa
[u
];if(!u
){u
=1;len
=0;}else{len
=min(len
,suf
.len
[u
])+1;u
=suf
.ch
[u
][c
];}if(u
>1&&!tag
[suf
.fa
[u
]]) tag
[suf
.fa
[u
]]=i
;sf
[i
].push_back((Qry
){len
,suf
.pos
[u
]});} for(int i
=suf
.tot
;i
>=1;i
--){int u
=suf
.id
[i
];if(!tag
[u
]) continue;if(!tag
[suf
.fa
[u
]]||tag
[suf
.fa
[u
]]<tag
[u
]) tag
[suf
.fa
[u
]]=tag
[u
];sf
[tag
[u
]].push_back((Qry
){suf
.len
[u
],suf
.pos
[u
]});}ans
=0;for(int i
=m
;i
>=1;i
--){for(int j
=0;j
<pf
[i
].size();j
++){Qry q
=pf
[i
][j
];ans
=max(ans
,q
.length
+query(n
-q
.p
));}for(int j
=0;j
<sf
[i
].size();j
++){Qry q
=sf
[i
][j
];if(q
.p
) update(q
.p
,q
.length
);}}printf("%d\n",ans
);return 0;
}
總結(jié)
以上是生活随笔為你收集整理的[XSY] 最长公共子串对（后缀自动机）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
