LeetCode Weekly Contest 136 : 1044. Longest Duplicate Substring

これはさすがに…。
https://leetcode.com/contest/weekly-contest-136/problems/longest-duplicate-substring/

問題

文字列が与えられる。
異なる始点から取った2つのsubstringのうち、最長のものを1つ答えよ。

解法

SuffixArrayがあれば自明。

struct SuffixArray {
int N; vector rank,lcp,sa,rsa; string S;

SuffixArray(string S) : S(S){
int i,h=0; vector tmp;
N=S.size(); rank.resize(N+1); sa.resize(N+1); tmp.resize(N+1);
FOR(i,N+1) sa[i]=i, rank[i]=i==N?-1:S[i];

for(int k=1; k<=N; k<<=1) {
auto pred2 = [k,this](int& a,int &b)->bool{ return (((a+k<=N)?rank[a+k]:-1)<*1;};
auto pred = [pred2,k,this](int& a,int &b)->bool{ return (rank[a]!=rank[b])?(rank[a]sa.lcp[p]) p=i;
}
return S.substr(sa.sa[p],sa.lcp[p]);
}
};

まとめ

これ日ごろ他のコンテスト出てる人は瞬殺だよなぁ。
木構造に関する問題が無いのは珍しいね。

*1:b+k<=N)?rank[b+k]:-1