【SPOJ220】Relevant Phrases of Annihilation（后缀数组，二分）

2021-06-28 17:04

阅读：706

标签：png getchar span 后缀数组 ras min har cas break

题意：技术分享图片

思路：

技术分享图片

  1 #include  2 #include  3 #includestring>
  4 #include  5 #include  6 #include
  7 #include  8 #includeset>
  9 #include 10 #include 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pairint,int> PII;
 16 typedef vectorint> VI;
 17 #define fi first
 18 #define se second 
 19 #define MP make_pair
 20 #define N   210000
 21 #define MOD 1000000007
 22 #define eps 1e-8 
 23 #define pi acos(-1)
 24 #define oo  1000000000
 25 
 26 char ch[N];
 27 
 28 int n,i,s[N],sa[N],wa[N],wb[N],wc[N],wd[N],height[N],rank[N],
 29     a[N],b[N],c[N],d[N],num[N],M;
 30 
 31 int read()
 32 { 
 33    int v=0,f=1;
 34    char c=getchar();
 35    while(c48||57if(c==‘-‘) f=-1; c=getchar();}
 36    while(4857) v=(v3)+v+v+c-48,c=getchar();
 37    return v*f;
 38 }
 39 
 40 bool cmp(int *r,int a,int b,int l)
 41 {
 42     return r[a]==r[b]&&r[a+l]==r[b+l];
 43 }
 44 
 45 void getsa(int *r,int *sa,int n,int m)
 46 {
 47     int *x=wa,*y=wb,j,p;
 48     for(i=0;i;
 49     for(i=1;i1];
 50     for(i=n-1;i>=0;i--) sa[--wc[x[i]]]=i;
 51     for(j=1,p=1;p2,m=p)
 52     {
 53         p=0;
 54         for(i=n-j;ii;
 55         for(i=0;i)
 56          if(sa[i]>=j) y[p++]=sa[i]-j;
 57         for(i=0;ix[y[i]];
 58         for(i=0;i0;
 59         for(i=0;i;
 60         for(i=1;i1];
 61         for(i=n-1;i>=0;i--) sa[--wc[wd[i]]]=y[i];
 62         swap(x,y);
 63         p=1; x[sa[0]]=0;
 64         for(i=1;i1],sa[i],j)?p-1:p++;
 65     }
 66 }
 67 
 68 void getheight(int *r,int *sa,int n)
 69 {
 70     int i,j,k=0;
 71     for(i=1;ii;
 72     for(i=0;ik)
 73     {
 74         if(k) k--;
 75         j=sa[rank[i]-1];
 76         while(r[i+k]==r[j+k]) k++;
 77     }
 78 }
 79 
 80 void init()
 81 {    
 82         memset(s,0,sizeof(s));
 83         memset(sa,0,sizeof(sa));
 84         memset(wa,0,sizeof(wa));
 85         memset(wb,0,sizeof(wb));
 86         memset(wc,0,sizeof(wc));
 87         memset(wd,0,sizeof(wd));
 88         memset(height,0,sizeof(height));
 89         memset(rank,0,sizeof(rank));
 90 }
 91     
 92 bool isok(int K)
 93 {
 94     int i=1;
 95     while(in)
 96     {
 97         i++;
 98         if(height[i]>=K)
 99         {
100             int st=i;
101             while(i=K) i++;
102             if(st1) 
103             {
104                 int ed=i-1;
105                 for(int j=1;j)
106                 {
107                     b[j]=0;
108                     c[j]=oo;
109                     d[j]=-oo;
110                 }
111                 for(int j=st-1;j) 
112                 {
113                     int t=num[sa[j]];
114                     b[t]++;
115                     c[t]=min(c[t],sa[j]);
116                     d[t]=max(d[t],sa[j]);
117                 }
118                 int flag=1;
119                 for(int j=1;j)
120                 {
121                       if(b[j]2){flag=0; break;}
122                       if(d[j]-c[j]0; break;}
123                 }
124                 if(flag) return 1;
125             }
126         }
127     }
128     return 0;
129 }
130 
131 int main()
132 {
133     freopen("spoj220.in","r",stdin);
134     freopen("spoj220.out","w",stdout); 
135     int cas;
136     scanf("%d",&cas); 
137     while(cas--)
138     {
139         init();
140         scanf("%d",&M);
141         n=-1;
142         for(int i=1;i) 
143         {
144             scanf("%s",ch);
145             int t=strlen(ch);
146             for(int j=0;j) 
147             {
148                 s[++n]=ch[j]-‘a‘+20;
149                 num[n]=i;
150             }
151             s[++n]=i;
152             num[n]=0;
153         }
154         getsa(s,sa,n+1,100);
155         getheight(s,sa,n);
156     //    printf("1\n"); 
157         int L=1;
158         int R=10000;
159         int last=0;
160         while(LR)
161         {
162             int mid=(L+R)>>1;
163             if(isok(mid)){last=mid; L=mid+1;}
164              else R=mid-1;
165         }
166         printf("%d\n",last);
167     }
168     return 0;
169 }
170

【SPOJ220】Relevant Phrases of Annihilation（后缀数组，二分）

标签：png getchar span 后缀数组 ras min har cas break

原文地址：https://www.cnblogs.com/myx12345/p/9648810.html

上一篇：《Python》网络编程之黏包

下一篇：《汇编语言基于x86处理器》第十章结构和宏部分的代码

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【SPOJ220】Relevant Phrases of Annihilation（后缀数组，二分）
文章链接：http://soscw.com/essay/98980.html

亲，登录后才可以留言！

【SPOJ220】Relevant Phrases of Annihilation（后缀数组，二分）

评论

热门文章

推荐文章

最新文章

置顶文章