POJ 1743(接尾辞配列+重複しない最長重複サブ列)
13758 ワード
タイトルリンク: http://poj.org/problem?id=1743
楼教主の男八题orz.1編のピアノ譜で、各メロディーの値は1~88以内です.琴譜のある段は変調し、つまりある段の数は1つの旋律範囲の値を加減することができる.このスペクトル内で最も長く重ならない重複部分の大きさを聞く.
問題解決の考え方:
ネット上の問題解が氾濫している問題.多くの細部が先輩大神にまとめられた.
接尾辞配列がまだ人気がなかった頃、この問題は確かに神題だった.
まず、メロディの変調の処理:
たとえば123123,ans=3です.
変調後:456123,ans=0?いいえans=3です.
メロディの初期値は使用できません.各旋律の前後の差を取るべきで、このようにある段がどんなに変調しても、元と同じであることを保証することができます.
しかし、これでn-1のメロディーになり、ansは-1になり、筆算でいくつかのグループを見ることができます.
差分値をとったn−1旋律についてSAとLCPを計算した. PS.多くの人がSAテンプレートに問題があり、自動末尾補0のSAテンプレートを推奨しており、問題が発生しにくい.
重複しない重複部分の大きさを要求し、ここではネット上でN回伝承されている奇抜な結論を採用した.
height配列をグループ化すると、各グループ内の接尾辞間のheightはlenより大きくなり、各グループ内の接尾辞間の最長共通接頭辞がlenより大きく、この2つの接尾辞のSAの差がlenより大きい場合、少なくともlenの長さの重複しないサブ列が存在することを示す.最長の共通接頭辞を求めるにはheight配列が使用されます.このグループの任意の2つの接尾辞の共通接頭辞は必ずいくつかのheight値の最小値であり、この値が最大であれば、このグループのheightの最大値である必要があります.
SA配列は辞書順であるため,二分SA配列長である.lenが要求に合致する場合は、先に記録します.もっと大きいのを右に探してください.そうしないと左に行きます.注意2点のときansの初期値は0で、さもなくばn=1のとき、2点がなくて1つのansをreturnしたことに等しい.
13560509
neopenx
1743
Accepted
840K
407MS
C++
2761B
2014-10-24 10:20:38
楼教主の男八题orz.1編のピアノ譜で、各メロディーの値は1~88以内です.琴譜のある段は変調し、つまりある段の数は1つの旋律範囲の値を加減することができる.このスペクトル内で最も長く重ならない重複部分の大きさを聞く.
問題解決の考え方:
ネット上の問題解が氾濫している問題.多くの細部が先輩大神にまとめられた.
接尾辞配列がまだ人気がなかった頃、この問題は確かに神題だった.
まず、メロディの変調の処理:
たとえば123123,ans=3です.
変調後:456123,ans=0?いいえans=3です.
メロディの初期値は使用できません.各旋律の前後の差を取るべきで、このようにある段がどんなに変調しても、元と同じであることを保証することができます.
しかし、これでn-1のメロディーになり、ansは-1になり、筆算でいくつかのグループを見ることができます.
差分値をとったn−1旋律についてSAとLCPを計算した. PS.多くの人がSAテンプレートに問題があり、自動末尾補0のSAテンプレートを推奨しており、問題が発生しにくい.
重複しない重複部分の大きさを要求し、ここではネット上でN回伝承されている奇抜な結論を採用した.
height配列をグループ化すると、各グループ内の接尾辞間のheightはlenより大きくなり、各グループ内の接尾辞間の最長共通接頭辞がlenより大きく、この2つの接尾辞のSAの差がlenより大きい場合、少なくともlenの長さの重複しないサブ列が存在することを示す.最長の共通接頭辞を求めるにはheight配列が使用されます.このグループの任意の2つの接尾辞の共通接頭辞は必ずいくつかのheight値の最小値であり、この値が最大であれば、このグループのheightの最大値である必要があります.
SA配列は辞書順であるため,二分SA配列長である.lenが要求に合致する場合は、先に記録します.もっと大きいのを右に探してください.そうしないと左に行きます.注意2点のときansの初期値は0で、さもなくばn=1のとき、2点がなくて1つのansをreturnしたことに等しい.
#include "cstring"
#include "cstdio"
#include "string"
#include "iostream"
using namespace std;
#define maxn 23000
int n,r[maxn],tmp[maxn];
template <class T>
inline bool read(T &ret)
{
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
struct Suffix
{
int sa[maxn],rk[maxn],height[maxn];
int t[maxn],t2[maxn],c[maxn],m;
void init() {m=200;}
int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];}
void build()
{
int i,k,p,*x=t,*y=t2;
r[n++]=0;
for (i=0; i<m; i++) c[i]=0;
for (i=0; i<n; i++) c[x[i]=r[i]]++;
for (i=1; i<m; i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) sa[--c[x[i]]]=i;
for (k=1,p=1; k<n; k*=2,m=p)
{
for (p=0,i=n-k; i<n; i++) y[p++]=i;
for (i=0; i<n; i++) if (sa[i]>=k) y[p++]=sa[i]-k;
for (i=0; i<m; i++) c[i]=0;
for (i=0; i<n; i++) c[x[y[i]]]++;
for (i=1; i<m; i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;
x[sa[0]]=0;
for (i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;
}
n--;
}
void LCP()
{
int i,j,k=0;
for (i=1; i<=n; i++) rk[sa[i]]=i;
for (i=0; i<n; i++)
{
if (k) k--;
j=sa[rk[i]-1];
while (r[i+k]==r[j+k]) k++;
height[rk[i]]=k;
}
}
bool judge(int len)
{
int l=sa[1],r=sa[1];
for(int i=2;i<=n;i++)
{
if(height[i]<len)
{
l=sa[i];r=sa[i];
continue;
}
l=min(l,sa[i]);
r=max(r,sa[i]);
if(r-l>len) return true;
}
return false;
}
int BinarySearch()
{
int l=0,r=n,mid,ans=0;// ans=0, n=1 ans
while(l<=r)
{
int mid=l+(r-l)/2;
if(judge(mid)) {ans=mid;l=mid+1;}
else r=mid-1;
}
return ans;
}
};
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out1.txt","w",stdout);
while(read(n)&&n)
{
for(int i=0; i<n; i++) read(tmp[i]);
for(int i=0; i<n-1; i++) {r[i]=tmp[i+1]-tmp[i]+90;}
Suffix a;
a.init();
a.build();
a.LCP();
int ans=a.BinarySearch();
if(ans<4) printf("0
");
else printf("%d
",ans+1);
}
}
13560509
neopenx
1743
Accepted
840K
407MS
C++
2761B
2014-10-24 10:20:38