POJ 1743 뮤지컬 테마(접미사 배열)
2467 단어 theme
제목:가장 긴 중복 되 지 않 는 문자열 을 찾 아 라.
사고방식:h 수조,2 분 답안 k 를 구하 고 k 에 따라 h 조 를 나눈다.각 조 의 임의의 두 꼬치 는 접두사 가 k 보다 크다 는 것 을 만족 시 킵 니 다.이 문자열 의 위치 최대 최소 치 를 구하 고 차이 가 k 보다 크 면 됩 니 다.
int r[N],sa[N],wa[N],wb[N],wd[N],rank[N],h[N];
int cmp(int *r,int a,int b,int L)
{
return r[a]==r[b]&&r[a+L]==r[b+L];
}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
FOR0(i,m) wd[i]=0;
FOR0(i,n) wd[x[i]=r[i]]++;
FOR1(i,m-1) wd[i]+=wd[i-1];
FORL0(i,n-1) sa[--wd[x[i]]]=i;
for(j=1,p=1;p<n;j<<=1,m=p)
{
p=0;
FOR(i,n-j,n-1) y[p++]=i;
FOR0(i,n) if(sa[i]>=j) y[p++]=sa[i]-j;
FOR0(i,m) wd[i]=0;
FOR0(i,n) wd[x[i]]++;
FOR1(i,m-1) wd[i]+=wd[i-1];
FORL0(i,n-1) sa[--wd[x[y[i]]]]=y[i];
t=x;x=y;y=t;p=1;x[sa[0]]=0;
FOR1(i,n-1) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void calHeight(int *r,int *sa,int n)
{
int i,j,k=0;
FOR1(i,n) rank[sa[i]]=i;
FOR0(i,n)
{
if(k) k--;
j=sa[rank[i]-1];
while(i+k<n&&j+k<n&&r[i+k]==r[j+k]) k++;
h[rank[i]]=k;
}
}
int n;
int OK(int x)
{
int i=2,j,L,R,Max,Min;
while(i<=n)
{
L=i;
while(L<=n&&h[L]<x) L++;
R=L;
while(R+1<=n&&h[R+1]>=x) R++;
if(R>n) return 0;
Max=-INF,Min=INF;
FOR(j,L,R)
{
Max=max(Max,max(sa[j],sa[j-1]));
Min=min(Min,min(sa[j],sa[j-1]));
}
if(Max-Min>=x) return 1;
i=R+1;
}
return 0;
}
void cal()
{
int low=0,high=n,mid;
while(low<=high)
{
mid=(low+high)>>1;
if(OK(mid)) low=mid+1;
else high=mid-1;
}
int ans;
if(low<=n&&OK(low)) ans=low+1;
else ans=high+1;
if(ans<5) ans=0;
PR(ans);
}
int main()
{
while(scanf("%d",&n),n)
{
int i,pre,cur;
RD(pre);
FOR0(i,n-1) RD(cur),r[i]=cur-pre+100,pre=cur;
n--;
r[n]=0;
da(r,sa,n+1,200);
calHeight(r,sa,n);
cal();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Storybook용 사용자 정의 툴바 애드온을 만드는 방법은 무엇입니까?Storybook을 사용하면 프레임워크에 관계없이 UI 요소의 프로토타이핑 속도를 높일 수 있습니다. 이 기사에서는 스토리북용 툴바 애드온을 만드는 방법을 살펴보겠습니다. 이 항목의 예는 사용자 지정 도구 모음 메뉴...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.