Codeforces Round #401 (Div. 2) D. Cloud of Hashtags

題目鏈接：D. Cloud of Hashtags

題意：

給你n個字符串，讓你刪后綴，使得這些字符串按字典序排列，要求是刪除的后綴最少

題解：

由于n比較大，我們可以將全部的字符串存在一個數組里面，然后記錄一下每個字符串的開始位置和長度，然后從下面往上對比。

如果str[i][j]<str[i+1][j]，直接退出，因為這里已經成為字典序。

如果str[i][j]>str[i+1][j],那么就把str[i][j]=0，表示從這里開始的后綴全部刪掉。

str[i][j]==str[i+1][j]就繼續尋找。

注意：數組要開N*3，因為包括結束符。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=5e5+7;
 7 char str[N*3];
 8 int st[N],len[N],n,ed;
 9 
10 char find(int i,int j){return str[st[i]+j];}
11 
12 inline void output(int s)
13 {
14     int now=s;
15     while(1)
16     {
17         if(!str[now])return;
18         putchar(str[now++]);
19     }
20 }
21 
22 int main(){
23     scanf("%d",&n);
24     F(i,1,n)
25     {
26         st[i]=ed;
27         scanf("%s",str+ed);
28         len[i]=strlen(str+ed);
29         ed+=len[i]+1;
30     }
31     for(int i=n-1;i>0;i--)
32     {
33         F(j,1,len[i]-1)
34         {
35             int tmp=find(i+1,j)-find(i,j);
36             if(tmp<0)
37             {
38                 str[st[i]+j]=0;
39                 break;
40             }if(tmp>0)break;
41         }
42     }
43     F(i,1,n)output(st[i]),puts("");
44     return 0;
45 }

View Code

轉載于:https://www.cnblogs.com/bin-gege/p/6443768.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/255286.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/255286.shtml
英文地址，請注明出處：http://en.pswp.cn/news/255286.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！