【SPOJ687&POJ3693】Maximum repetition substring(后缀数组)

时间:2022-09-13 16:06:20

题意:

【SPOJ687&POJ3693】Maximum repetition substring(后缀数组)

n<=1e5

思路:

【SPOJ687&POJ3693】Maximum repetition substring(后缀数组)

From http://hzwer.com/6152.html

往后匹配多远 r 用ST表求lcp即可。。。往前 l 就把串反过来再做一下。。

但是有可能求出来的最长串可以前移/后移几位
即开头可以在落在[il,il+(l+r)mod L]

区间内字典序最小的还要用ST表找rank区间最值

有空需要学习一下结构体写法 一模一样的东西写多次太累了

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<set>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pair<int,int> PII;
 16 typedef vector<int> VI;
 17 #define fi first
 18 #define se second 
 19 #define MP make_pair
 20 #define N   110000
 21 #define MOD 1000000007
 22 #define eps 1e-8 
 23 #define pi acos(-1)
 24 #define oo  1000000000
 25 
 26 char ch[N];
 27 int n,i,s[N],sa[N],wa[N],wb[N],wc[N],wd[N],height[N],rank[N],
 28     ans,mx,ansl,ansr,f[4][N][20],g[3][N],save[N],Log[N],bin[N];
 29 
 30 
 31 int read()
 32 { 
 33    int v=0,f=1;
 34    char c=getchar();
 35    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 36    while(48<=c&&c<=57) v=(v<<3)+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<n;i++) wc[x[i]=r[i]]++;
 49     for(i=1;i<m;i++) wc[i]+=wc[i-1];
 50     for(i=n-1;i>=0;i--) sa[--wc[x[i]]]=i;
 51     for(j=1,p=1;p<n;j*=2,m=p)
 52     {
 53         p=0;
 54         for(i=n-j;i<n;i++) y[p++]=i;
 55         for(i=0;i<n;i++)
 56          if(sa[i]>=j) y[p++]=sa[i]-j;
 57         for(i=0;i<n;i++) wd[i]=x[y[i]];
 58         for(i=0;i<m;i++) wc[i]=0;
 59         for(i=0;i<n;i++) wc[wd[i]]++; 
 60         for(i=1;i<m;i++) wc[i]+=wc[i-1];
 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;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],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;i<=n;i++) rank[sa[i]]=i;
 72     for(i=0;i<n;height[rank[i++]]=k)
 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 int lcp(int p,int x,int y)
 93 {
 94     int t;
 95     int L=g[p][x];
 96     int R=g[p][y];
 97     if(L>R){t=L; L=R; R=t;}
 98     L++;
 99     int q=Log[R-L+1];
100     return min(f[p][L][q],f[p][R-bin[q]+1][q]);
101 }
102 
103 int query(int x,int y)
104 {
105     int q=Log[y-x+1];
106     return min(f[3][x][q],f[3][y-bin[q]+1][q]);
107 }
108 
109 void solve(int L)
110 {
111     for(int i=0;i+L<n;i+=L)
112     if(ch[i]==ch[i+L])
113     {
114         int r=lcp(1,i,i+L);
115     //    printf("1 %d %d %d\n",i,i+L,r);
116         int l=lcp(2,n-i,n-i-L);
117     //    printf("2 %d %d %d\n",n-i,n-i-L,l);
118         if((l+r)/L+1>mx) {mx=(l+r)/L+1; ans=oo;}
119         if((l+r)/L+1==mx)
120         {
121             int t=query(i-l,i-l+(l+r)%L);
122         //    printf("%d %d %d\n",i-l,i-l+(l+r)%L,t);
123             if(t<ans)
124             {
125                 ans=t;
126                 ansl=save[t];
127                 ansr=ansl+mx*L-1;
128             }
129         }
130     }
131 }
132 
133 int main()
134 {
135     //freopen("poj3693.in","r",stdin);
136     //freopen("poj3693.out","w",stdout); 
137     bin[0]=1;
138     for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
139     Log[0]=-1;
140     for(int i=1;i<=100000;i++) Log[i]=Log[i/2]+1;
141     int cas=0;
142     while(scanf("%s",ch))
143     {
144         if(ch[0]=='#') break;
145         cas++;
146         printf("Case %d: ",cas);
147          
148         init();
149          n=strlen(ch);
150          for(int i=0;i<n;i++) s[i]=ch[i]-'a'+1;
151          s[n]=0;
152          getsa(s,sa,n+1,100);
153          getheight(s,sa,n);
154          
155          for(int i=0;i<n;i++) f[3][i][0]=rank[i];
156          
157          int len=Log[n];
158          for(int i=2;i<=n;i++) f[1][i][0]=height[i];
159          for(int i=1;i<=len;i++)
160            for(int j=2;j+bin[i]-1<=n;j++)
161             f[1][j][i]=min(f[1][j][i-1],f[1][j+bin[i-1]][i-1]);
162         for(int i=0;i<=n;i++) g[1][i]=rank[i];
163         for(int i=0;i<=n;i++) save[i]=sa[i];
164         
165         init();
166         for(int i=0;i<n;i++) s[i]=ch[n-1-i]-'a'+1;
167          s[n]=0;
168          getsa(s,sa,n+1,100);
169          getheight(s,sa,n);
170 
171          for(int i=2;i<=n;i++) f[2][i][0]=height[i];
172          for(int i=1;i<=len;i++)
173            for(int j=2;j+bin[i]-1<=n;j++)
174            f[2][j][i]=min(f[2][j][i-1],f[2][j+bin[i-1]][i-1]);
175         for(int i=0;i<=n;i++) g[2][i]=rank[i];
176         
177         
178     
179         for(int i=1;i<=len;i++)
180            for(int j=0;j+bin[i]-1<=n-1;j++)
181            f[3][j][i]=min(f[3][j][i-1],f[3][j+bin[i-1]][i-1]);
182 
183         ansl=ansr=1;
184         mx=1; ans=oo;
185         for(int i=0;i<n;i++)
186          if(ch[i]<ch[ansl]){ans=1; ansl=ansr=i;} 
187         for(int i=1;i<=n;i++) solve(i);
188         for(int i=ansl;i<=ansr;i++) printf("%c",ch[i]);
189         printf("\n"); 
190     }
191     return 0;
192 }
193