【Poj-3693】Maximum repetition substring 後綴數組 連續重複子串
POJ – 3693
題意
SPOJ – REPEATS 的進階版，在這題的基礎上輸出字典序最小的重複字串。
思路
跟上題一樣，先求出最長的重複次數，在求的過程中順便紀錄最多次數可能的長度。
因為sa數組是按照字典序排好的，所以我們順序遍歷sa數組，找到第一個符合的輸出即可。
PS:
通過這題大致知道了為什麼之前看到有的後綴數組程式碼需要在字元串最後加一個0。
（我的模板是OI-wiki上的，沒有這一步，而且之前也沒錯過，可能是之前做過的題目數據沒有卡到，這題只有a和b，就很大可能會出問題）。
寫完之後一直有問題，還找不到bug，在網上看到一個程式碼，把相應的數組清零了，我就清零了rank數組，就過了，然後試了一下只把rank[n+1]變為0，也過了。
我就找了一下哪裡會出這個問題，猜可能是因為求height數組的時候，沒有判斷越界，所以height數組就可能出錯。類似下面
char str[100];
while(~scanf("%s",str))
{
for(int i=0;i<10;i++) printf("%c",str[i]);
printf("\n");
}
/*
input:
1111111111
0000
output:
1111111111
0000 11111
*/
加上越界判斷之後，不用清空rank，就過掉了。
所以加0，可能就是為了書寫方便。。。。
程式碼
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<math.h>
#define pb push_back
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1e5+10;
int sa[N],cnt[N],pos[N],rk[N],oldrk[N],ht[N],n,m;
char str[N];
bool cmp(int a,int b,int k)
{
return oldrk[a]==oldrk[b]&&oldrk[a+k]==oldrk[b+k];
}
void getsa()
{
memset(cnt,0,sizeof(cnt));
m=122;
for(int i=1; i<=n; ++i) ++cnt[rk[i]=str[i]];
rk[n+1]='c';//加之前沒有出現過的也可以
for(int i=1; i<=m; ++i) cnt[i]+=cnt[i-1];
for(int i=n; i; i--) sa[cnt[rk[i]]--]=i;
for(int k=1; k<=n; k<<=1)
{
int num=0;
for(int i=n-k+1; i<=n; ++i) pos[++num]=i;
for(int i=1; i<=n; ++i) if(sa[i]>k) pos[++num]=sa[i]-k;
memset(cnt,0,sizeof(cnt));
for(int i=1; i<=n; ++i) ++cnt[rk[i]];
for(int i=1; i<=m; ++i) cnt[i]+=cnt[i-1];
for(int i=n; i; i--) sa[cnt[rk[pos[i]]]--]=pos[i];
num=0;
memcpy(oldrk,rk,sizeof(rk));
for(int i=1; i<=n; ++i) rk[sa[i]]=cmp(sa[i],sa[i-1],k)?num:++num;
if(num==n) break;
m=num;
}
for(int i=1; i<=n; ++i)
rk[sa[i]]=i;
int k=0;
for(int i=1; i<=n; ++i)
{
if(k) --k;
while(str[i+k]==str[sa[rk[i]-1]+k]) ++k;
//下面就是加上越界判斷
// while(i+k<=n&&sa[rk[i]-1]+k<=n&&str[i+k]==str[sa[rk[i]-1]+k])
// ++k;
ht[rk[i]]=k;
}
}
int dp[N][20];
void RMQ()
{
for(int i=1; i<=n; ++i) dp[i][0]=ht[i];
for(int j=1; (1<<j)<=n; ++j)
{
for(int i=1; i+(1<<j)-1<=n; ++i)
dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int query(int l,int r)
{
int k=0;
while((1<<(k+1))<=(r-l+1)) ++k;
//int k=int(log(r-l+1.0)/log(2.0));// 比上面慢
return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int lcp(int i,int j)
{
i=rk[i],j=rk[j];
if(i>j) swap(i,j);
return query(i+1,j);
}
int tot,len[N];
int main()
{
int cas=0;
while(~scanf("%s",str+1)&&strcmp(str+1,"#"))
{
tot=0;
n=strlen(str+1);
getsa();
RMQ();
printf("Case %d: ",++cas);
int ans=0;
for(int i=1; i<=n; ++i)
{
for(int j=1; j+i<=n; j+=i)
{
int now=lcp(j,j+i);
int num=now/i+1;
int k=j-(i-now%i);
if(k>0&&lcp(k,k+i)>=i) ++num;
if(num>ans)
{
ans=num;
tot=0;
len[tot++]=i;
}
else if(num==ans)
{
if(len[tot-1]!=i)
len[tot++]=i;
}
}
}
int flag=0;
for(int i=1; i<=n; ++i)
{
for(int j=0; j<tot; ++j)
{
int l=len[j];
if(lcp(sa[i],sa[i]+l)>=(ans-1)*l)
{
str[sa[i]+ans*l]='\0';//使用結束符比一個個輸出快
printf("%s\n",str+sa[i]);
flag=1;
break;
}
}
if(flag)
break;
}
}
return 0;
}
/*
*/
