Oh! s**t bi——（屏蔽）
# 題面
給定一個長度為 \(n\) 的字串 \(S\) 和正整數數列 \(w_1,w_2,\cdots,w_n\)，記以第 \(i\) 個字符開頭的后綴為 \(S_i\)，
求 \(\max\limits_{i\neq j}\{\operatorname{LCP}(S_i,S_j)+(w_i\oplus w_j)\}\)，其中 \(\oplus\) 為按位異或，
資料規模：\(1\le n\le10^5\)，\(w_i< n\)，
# 決議
LCP？能夠快速求LCP的——SAM，哈希+二分……SA的height陣列？（雖然SAM也能做，但是感覺height陣列要清晰一些）
另外，我寫的 height[i] 表示的是 sa[i] 和 sa[i+1] 的 LCP，注意一下下標，
我們知道 \(LCP(S_i,S_j)\) 就是 rank[i] 和 rank[j] 之間的 height 的最小值，
不妨對 height 陣列的每個位置 \(i\)，考慮計算以 \(i\) 處為 height 最小值的一對 \(S_i,S_j\) 的 \(\max\{w_i\oplus w_j\}\)，如何求兩個數異或的最大值？Trie樹即可，（線性基是求若干個數的異或和）
那么怎么求有哪些 \(S_i,S_j\) 以 \(i\) 位置為 height 最小值？可以想到用笛卡爾樹，按根為區間最小值的方式建出 height 陣列的笛卡爾樹，
于是可以遞回地計算答案——
- 葉子 \(i\) 處答案為
height[i]+(w[i]^w[i+1])，笛卡爾樹中有兩個串：w[sa[i]],w[sa[i+1]]； - 非葉子節點 \(i\)，先考慮計算答案——列舉一棵子樹的中的所有串，在另一棵子樹的 Trie 樹中查答案，取最大值記為
mx，則答案為height[i]+mx，
但是如果隨便選一棵子樹列舉其中的所有串，每次復雜度顯然會降至 \(O(n\log n)\)，我們可以“聰明一點”，用啟發式的思想，列舉大小較小的一棵子樹中的串，在另一棵子樹的 Trie 中查，這樣總的復雜度就是 \(O(n\log^2n)\)，
最后兩棵子樹的 Trie 合并，該怎么合并怎么合并，至于復雜度：未合并時，Trie 的總點數為 \(O(n\log n)\)，每次合并的復雜度是合并的點數，每次合并后總點數會減少合并的點數，總復雜度 \(O(n\log n)\)，
這樣就可以在 \(O(n\log^2 n)\) 的復雜度內解決，
最后提一句——注意 Trie 樹存二進制的葉子節點的深度（在我的實作中葉子深度應為 \(-1\)），
# 源代碼
決議說起來還很快樂，但是代碼好像也不是特別短……
點擊展開/折疊代碼
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
#define con(type) const type &
inline int rin(int &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
namespace SA{
int rnk[N<<1],nrnk[N<<1],sa[N<<1],nsa[N<<1],hgt[N];
int bin[N];
void build(char *str,con(int)n){
for(int i=1;i<=n;i++) bin[str[i]-'a']++;
for(int i=1;i<30;i++) bin[i]+=bin[i-1];
for(int i=1;i<=n;i++) sa[bin[str[i]-'a']--]=i;
rnk[sa[1]]=1;
for(int i=2;i<=n;i++){
rnk[sa[i]]=rnk[sa[i-1]];
if(str[sa[i]]!=str[sa[i-1]]) rnk[sa[i]]++;
}
for(int len=1;rnk[sa[n]]<n;len<<=1){
for(int i=1;i<=n;i++) bin[rnk[sa[i]]]=i;
for(int i=n;i>=1;i--)
if(sa[i]>len)
nsa[bin[rnk[sa[i]-len]]--]=sa[i]-len;
for(int i=n-len+1;i<=n;i++)
nsa[bin[rnk[i]]--]=i;
nrnk[nsa[1]]=1;
for(int i=2;i<=n;i++){
nrnk[nsa[i]]=nrnk[nsa[i-1]];
if(rnk[nsa[i]]!=rnk[nsa[i-1]] || rnk[nsa[i]+len]!=rnk[nsa[i-1]+len])
nrnk[nsa[i]]++;
}
swap(rnk,nrnk),swap(sa,nsa);
}
}
void buildHeight(char *str,con(int)n){
for(int i=1,tmp=0;i<=n;i++){
if(tmp) tmp--;
while(str[i+tmp]==str[sa[rnk[i]-1]+tmp]) tmp++;
hgt[rnk[i]]=tmp;
}
}
}
struct SuperDeque{
int ary[N],le,ri;
void clear(){le=1,ri=0;}
void push_back(con(int)x){ary[++ri]=x;}
void pop_back(){ri--;}
void pop_front(){le++;}
int back(){return ary[ri];}
int front(){return ary[le];}
bool empty(){return le>ri;}
}que;
struct Trie{
int nxt[N*20][2],rt[N],ncnt;
int combine(con(int)u,con(int)v){
if(!u || !v) return u|v;
nxt[u][0]=combine(nxt[u][0],nxt[v][0]);
nxt[u][1]=combine(nxt[u][1],nxt[v][1]);
return u;
}
int query(con(int)u,con(int)num){
int ret=0;
for(int dep=16,v=u;~dep;dep--){
int dir=!(num>>dep&1);
if(nxt[v][dir]) v=nxt[v][dir],ret|=(1<<dep);
else v=nxt[v][!dir];
}
return ret;
}
int query(con(int)u,con(int)dep,con(int)num,con(int)v){
if(dep==-1) return query(v,num);
int ret=0;
if(nxt[u][0]) ret=max(ret,query(nxt[u][0],dep-1,num,v));
if(nxt[u][1]) ret=max(ret,query(nxt[u][1],dep-1,num|(1<<dep),v));
return ret;
}
void insert(int &u,con(int)dep,con(int)num){
if(!u) u=++ncnt;
if(dep==-1) return;
insert(nxt[u][num>>dep&1],dep-1,num);
}
int& operator [](con(int)u){return rt[u];}
}tri;
int n,ans;
int val[N],son[N][2];
char str[N];
int dacDFS(con(int)u){
if(!son[u][0] && !son[u][1]){
tri.insert(tri[u],16,val[SA::sa[u]]);
ans=max(ans,tri.query(tri[u],val[SA::sa[u+1]])+SA::hgt[u]);
tri.insert(tri[u],16,val[SA::sa[u+1]]);
return 2;
}
else if(!son[u][0]){
int ret=dacDFS(son[u][1])+1;
ans=max(ans,tri.query(tri[son[u][1]],val[SA::sa[u]])+SA::hgt[u]);
tri.insert(tri[son[u][1]],16,val[SA::sa[u]]);
tri[u]=tri[son[u][1]];
return ret;
}
else if(!son[u][1]){
int ret=dacDFS(son[u][0])+1;
ans=max(ans,tri.query(tri[son[u][0]],val[SA::sa[u+1]])+SA::hgt[u]);
tri.insert(tri[son[u][0]],16,val[SA::sa[u+1]]);
tri[u]=tri[son[u][0]];
return ret;
}
else{
int res0=dacDFS(son[u][0]),res1=dacDFS(son[u][1]);
if(res0<res1) ans=max(ans,tri.query(tri[son[u][0]],16,0,tri[son[u][1]]));
else ans=max(ans,tri.query(tri[son[u][1]],16,0,tri[son[u][0]]));
tri[u]=tri.combine(tri[son[u][0]],tri[son[u][1]]);
return res0+res1;
}
}
int main(){
rin(n),scanf("%s",str+1);
for(int i=1;i<=n;i++) rin(val[i]);
SA::build(str,n),SA::buildHeight(str,n);
for(int i=1;i<n;i++) SA::hgt[i]=SA::hgt[i+1];
// for(int i=1;i<n;i++) printf("! %d\n",SA::hgt[i]);
que.clear();
for(int i=1;i<n;i++){
int las=0;
while(!que.empty() && SA::hgt[que.back()]>SA::hgt[i]){
son[que.back()][1]=las;
las=que.back(),que.pop_back();
}
son[i][0]=las;
que.push_back(i);
}
int las=0;
while(!que.empty()){
son[que.back()][1]=las;
las=que.back(),que.pop_back();
}
// for(int i=1;i<n;i++) printf("%d %d\n",son[i][0],son[i][1]);
dacDFS(las);
printf("%d\n",ans);
return 0;
}
THE END
Thanks for reading!
若你是最悠長的宮音
我是清亮的羽
分離在琴弦的兩極 難相遇
縱然是再遙遠的距離
也愿與你相依
只等那一曲琴聲起 和鳴
——《琴弦上(vocaloid)》By 樂正綾/赤羽/星葵
> Link 琴弦上-Bilibili
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264405.html
標籤：其他
上一篇：演算法 字串類問題(一)