접미사 배열 모드
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
const int maxn=100009;
int s[maxn],sa[maxn],len,c[maxn],t[maxn],t2[maxn];
void build_sa(int *s,int *sa,int n,int m)//s ，sa ，n， ，m ，
{
int i,*x=t,*y=t2;
for (int i=0;i<m;i++) c[i]=0;
for (int i=0;i<n;i++) c[x[i]=s[i]]++;
for (int i=1;i<m;i++) c[i]=c[i-1]+c[i];
for (int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for (int k=1;k<=n;k<<=1)
{
int p=0;
for (int i=n-k;i<n;i++) y[p++]=i;
for (int i=0;i<n;i++)if (sa[i]>=k) y[p++]=sa[i]-k;
for (int i=0;i<m;i++) c[i]=0;
for (int i=0;i<n;i++) c[x[y[i]]]++;
for (int i=1;i<m;i++) c[i]=c[i-1]+c[i];
for (int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;
x[sa[0]]=0;
for (int i=1;i<n;i++)
x[sa[i]]= (y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]? p-1:p++);
if (p>=n) break;
m=p;
}
}
int main()
{
cin>>len;
for (int i=0;i<len;i++)
{
char ch;
cin>>ch;
s[i]=ch-'a'+1;
}
s[len]=0;//
build_sa(s,sa,len+1,26);// ， len+1
//for (int i=1;i<=len;i++) cout<<sa[i]<<' ';
return 0;
}
마지막 으로 몇 문제 연습 문 제 를 드 리 겠 습 니 다.
• Poj 2774 – 최 장 공공 연속 서브 꼬치, 입문 문제
• Poj 1743 - 최 장 중복 하위 문자열
• Hint: 2 점 판정 은 조심해 야 합 니 다. 이 문 제 는 좀 특별 합 니 다.
• Poj 3294 - 절반 이 넘 는 최 장 자 꼬치 등장
• Hint: 팀 에 나타 난 횟수 를 판단 하 는 기술 이 중요 합 니 다.
• Poj 3261 - k 회 반복 하면 하위 문자열 을 중첩 할 수 있 습 니 다.
• Hint: 위의 두 문 제 를 알 게 되 었 습 니 다. 이 문 제 는 아주 간단 할 것 입 니 다. 단조 로 운 스 택 을 사용 해 보 세 요.
• Poj 2758 - 접미사 배열 + rmq
• Hint: 이 문 제 는 rmq 가 아니 라 코드 를 쓰 는 능력 과 조회 알고리즘 에 의 해 이 루어 집 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
