題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長(zhǎng)度為 $n$ 的字符串 $s$，對(duì)于每個(gè)前綴來說，求出字典序最大的子串。

題目分析：看到子串的字典序，感覺能用后綴樹來做，參考了一下大佬的賽上代碼： 香港中文大學(xué)（深圳）- 新手上路

需要觀察出本題的一個(gè)結(jié)論就是，答案一定是一個(gè)前綴的后綴，所以我們只需要求出每個(gè)答案子串的左端點(diǎn)即可。

按照套路，對(duì)原串建立后綴樹，按照字典序跑出 dfs 序 $dfn$，順便維護(hù)一下每個(gè)節(jié)點(diǎn)首次出現(xiàn)的 $endpos$ 。

然后就可以用優(yōu)先隊(duì)列貪心了。記前綴 $pre[i]=s[1]s[2]?s[i]$，對(duì)于 $pre[n]$ 來說，我們只需要從 $parent$ 樹的葉子結(jié)點(diǎn)里，選擇 $dfn$ 最大的那個(gè)葉子結(jié)點(diǎn)作為答案即可。

而對(duì)于 $pre[n?1]$ 來說，需要將過期的結(jié)點(diǎn)淘汰，更具體的，如果一個(gè)結(jié)點(diǎn)所代表的字符串，已經(jīng)不在 $pre[n?1]$ 所表示的前綴中出現(xiàn)，我們需要在邏輯上刪掉這個(gè)葉子結(jié)點(diǎn)，同時(shí)判斷一下其父節(jié)點(diǎn)是否會(huì)成為一個(gè)新的葉子結(jié)點(diǎn)。

時(shí)間復(fù)雜度 $O(n\log n)$，感覺隨便就可以卡掉。。

代碼：

// Problem: String Problem // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/24346/M // Memory Limit: 1048576 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; char s[N]; vector<int>node[N<<1]; int tot,last,endpos[N<<1]; int dfn[N<<1],du[N<<1],cnt; int ans[N]; struct Node {int ch[26];int fa,len; }st[N<<1]; inline int newnode() {tot++;for(int i=0;i<26;i++)st[tot].ch[i]=0;st[tot].fa=st[tot].len=0;endpos[tot]=0;node[tot].clear();return tot; } void add(int x) {int p=last,np=last=newnode();st[np].len=st[p].len+1;while(p&&!st[p].ch[x])st[p].ch[x]=np,p=st[p].fa;if(!p)st[np].fa=1;else{int q=st[p].ch[x];if(st[p].len+1==st[q].len)st[np].fa=q;else{int nq=newnode();st[nq]=st[q]; st[nq].len=st[p].len+1;st[q].fa=st[np].fa=nq;while(p&&st[p].ch[x]==q)st[p].ch[x]=nq,p=st[p].fa;//向上把所有q都替換成nq}} } void dfs_pos(int u) {for(auto v:node[u]) {dfs_pos(v);endpos[u]=max(endpos[u],endpos[v]);} } void dfs(int u) {dfn[u]=++cnt;sort(node[u].begin(),node[u].end(),[&](int x,int y) {return s[endpos[x]-st[u].len]<s[endpos[y]-st[u].len];});for(auto v:node[u]) {dfs(v);} } void build() {for(int i=1;i<=tot;i++) {node[st[i].fa].push_back(i);du[st[i].fa]++;}dfs_pos(1);dfs(1); } void init() {last=1;cnt=tot=0;newnode(); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%s",s+1);init();int n=strlen(s+1);reverse(s+1,s+1+n);for(int i=1;i<=n;i++) {add(s[i]-'a');endpos[last]=i;}build();priority_queue<pair<int,int>>q;for(int i=1;i<=tot;i++) {if(!du[i]) {q.push({dfn[i],i});}}for(int i=n;i>=1;i--) {while(1) {int u=q.top().second;int fa=st[u].fa;int l=n-endpos[u]+1;int r=l+st[fa].len;if(r>i) {q.pop();if(--du[fa]==0&&fa!=1) {q.push({dfn[fa],fa});}} else {ans[i]=l;break;}}}for(int i=1;i<=n;i++) {printf("%d %d\n",ans[i],i);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021ICPC(沈阳) - String Problem(后缀树+贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。