접미사 배열 2 배증 알고리즘 독서 노트
7444 단어 접미사 배열
우선 접미사 배열 의 2 배 증가 알고리즘 을 묘사 하 겠 습 니 다.관련 개념 몇 가 지 를 살 펴 보 자.
1. 하위 문자열: 문자열 의 연속 부분;
2. 접미사: 마지막 문 자 는 전체 문자열 의 끝 문자 인 특수 문자열 입 니 다.
3. 접미사 배열: sa [] 는 특정한 1 - n 의 배열 입 니 다. 구체 적 으로 말 하면 주어진 문자열 의 n 개의 접 두 사 를 사전 순서에 따라 작은 것 에서 큰 것 으로 배열 한 다음 에 이 접미사 에 대응 하 는 시작 위 치 를 sa [] 에 저장 하고 suffix (sa [i]) < suffix (sa [i + 1]) 를 확보 합 니 다.
4. 순위 배열: rank [] 은 시작 위치 에서 n 개의 접 두 사 를 순서대로 저장 하고 접두사 배열 과 서로 거 스 릅 니 다.
접미사 배열 sa [] 는 몇 번 째 가 누구 인지, 순위 배열 rank [] 은 누가 몇 번 째 인지 표시 합 니 다.체득 을 구별 하 는 데 주의해 라.
2 배증 알고리즘 에 대한 설명:
배가 사상 과 기수 로 정렬 하여 각 위치 에서 시 작 된 2 ^ k 문 자 를 정렬 하여 랭 킹 [] 을 구하 고 sa [] 를 유지 한 다음 에 k + + 는 각 위치 에서 시 작 된 2 ^ (k + 1) 문 자 를 정렬 하여 랭 킹 [] 을 구하 고 sa [] 를 유지 합 니 다.............................................................어떤 위치 에서 시 작 된 2 ^ k 글자 의 순위 rank [] 를 구 합 니 다. 이 위 치 를 시작 으로 하 는 2 ^ k 글자 의 순위 rank [] 와 그 다음 위치 에서 시 작 된 2 ^ k 글자 의 순위 rank [] 를 결합 하여 기수 순 서 를 이용 하여 해결 합 니 다.
자신의 말 이 틀 리 는 것 을 방지 하기 위해 다음 과 같은 원문의 설명 을 참조 합 니 다.
배가 알고리즘 의 주요 사고방식 은 배가 되 는 방법 으로 각 문자 의 시작 길이 가 2k 인 하위 문자열 을 정렬 하여 순위, 즉 rank 값 을 구 하 는 것 이다.k 는 0 부터 매번 1 을 추가 합 니 다. 2k 가 n 보다 크 면 모든 문자 의 시작 길이 가 2k 인 하위 문자열 은 모든 접미사 에 해당 합 니 다.또한 이 하위 문자열 들 은 모두 크기 를 비교 해 야 합 니 다. 즉, rank 값 에 같은 값 이 없 으 면 이때 rank 값 이 마지막 결과 입 니 다.매번 정렬 할 때마다 마지막 길이 가 2k - 1 인 문자열 의 rank 값 을 이용 합 니 다. 그러면 길이 가 2k 인 문자열 은 두 개의 길이 가 2k - 1 인 문자열 의 순 위 를 키워드 로 표시 한 다음 에 기수 정렬 을 하면 길이 가 2k 인 문자열 의 rank 값 을 얻 을 수 있 습 니 다.
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
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;
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[x[i]=r[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
， ， 。
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
//
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;//
for(i=0;i<m;i++) ws[i]=0;// 0
for(i=0;i<n;i++) ws[x[i]=r[i]]++;//x[i]=r[i],x[] 1h ;ws[] ; ws[] 1hsa[]
for(i=1;i<m;i++) ws[i]+=ws[i-1];//ws[]
for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;// ， ， 1h 0-n-1，
for(j=1,p=1;p<n;j*=2,m=p)
{
//
for(p=0,i=n-j;i<n;i++) y[p++]=i;// n-j n 0， ， 。
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;//if(sa[i]>=j)， j j
for(i=0;i<n;i++) wv[i]=x[y[i]];//
for(i=0;i<m;i++) ws[i]=0;//
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];// ， ， 1h 0-n-1，
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)// x[] rank ， ， sa[] ， rank rank， p==n
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
이상 은 접미사 배열 의 실현 템 플 릿 입 니 다. 즉, sa [] 를 구 했 습 니 다. 그러나 접미사 배열 을 구체 적 으로 활용 하려 면 해당 하 는 height [] 배열 에 맞 춰 야 합 니 다.다음은 height [] 배열 의 구현 템 플 릿 입 니 다:
int rank[MAXN],height[MAXN];
// height[i]=suffix(sa[i-1]) suffix(sa[i])
// ，
// i,j( rank[i]<rank[j])
// height[rank[i]+1]、height[rank[i]+2]…height[rank[j]]
void calheight(char *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
return;
}
height [] 배열 을 바탕 으로 접미사 배열 은 문자열 일치 등에 있어 독특한 장점 을 가진다.
sa [] 의 시간 복잡 도 를 O (N * log (N) 로 구 합 니 다.height [] 를 구 하 는 시간 복잡 도 는 O (N) 이 고 알고리즘 이 효율 적 인 응용 을 요구 하 는 상황 에서 이들 은 모두 받 아들 일 수 있다.
1. 최 장 공통 접두사
두 접미사 의 가장 긴 공공 접 두 사 를 요구 하 는 문자열 을 지정 합 니 다.
height [i] = suffix (sa [i - 1]) 와 suffix (sa [i]) 의 최 장 공 / 공 접두사, 즉 순위 가 인접 한 두 접두사 의 최 장 공공 접두사 입 니 다.원 하 는 것 은 height [] 배열 의 최대 값 이 고 미리 처리 한 상황 에서 시간 복잡 도 는 O (1) 입 니 다.RMQ 문제 에 대해 서 는 height [] 배열 의 구간 최 값, 즉 [l, r] 구간 내 height [] 의 최소 값 을 먼저 구 할 수 있 습 니 다.왜 최소 치 죠?임의의 두 개의 시작 위치 가 i 이기 때문에 j (rank [i] < rank [j]) 의 접미사 의 최 장 공공 접두사 / / height [rank [i] + 1], height [rank [i] + 2]... height [rank [j] 의 최소 값 입 니 다.RMQ 문 제 는 ST 알고리즘 으로 시간 복잡 도 O (N * log (N) 내 에서 해결 할 수 있다.
참고 할 만 한 예제 가 있다.
http://blog.csdn.net/xj2419174554/article/details/10163209
2. 최 장 반복 문자열 중첩 가능
문자열 을 지정 합 니 다. 가장 긴 중복 문자열 을 구하 십시오. 이 두 문자열 은 겹 칠 수 있 습 니 다.
어떤 하위 문자열 은 반드시 어떤 접두사 의 접두사 이 고, 가장 긴 중복 문자열 은 두 접두사 의 가장 긴 공공 접두사 이다.그래서 height [] 의 최소 값 으로 바 뀌 었 다.
3. 최 장 중복 하위 문자열 중첩 불가
문자열 을 지정 합 니 다. 가장 긴 중복 문자열 을 구 합 니 다. 이 두 문자열 은 겹 칠 수 없습니다.
겹 치지 않 는 다 는 것 은 간단하게 반복 할 수 없다 는 것 을 의미한다.만족 하면 두 길이 가 len 인 하위 문자열 이 똑 같 고 중첩 되 지 않 는 다 는 것 을 의미한다. 이때 오른쪽으로 이동 하고 두 분 구 간 의 하 계 를 이동 해 야 한다.만족 하지 않 으 면 왼쪽으로 이동 하고 두 분 구 간 의 상계 로 이동 해 야 한다.height [] 를 처리 하 는 토대 에서 2 분 의 시간 복잡 도 는 O (N * log (N) 이다.
참고 할 만 한 예제 가 있다.http://blog.csdn.net/xj2419174554/article/details/10171207
4. 겹 칠 수 있 는 k 회 최 장 반복 문자열
최소한 k 번 의 최 장 중복 문자열 이 나타 나 도록 문자열 을 지정 합 니 다. 이 k 문자열 은 겹 칠 수 있 습 니 다.
우 리 는 위의 문제 처럼 하위 문자열 의 길 이 를 2 분 의 1 로 나 눌 수 있 습 니 다. 그리고 len 대 height [] 배열 에 따라 세그먼트 를 나 눌 수 있 습 니 다. 아래 표 는 연속 적 이 고 height [i] > = len 은 반드시 같은 세그먼트 에 있어 야 합 니 다. 그래서 이 세그먼트 의 이 세그먼트 내 요소 의 개수 가 k - 1 보다 큰 지 를 보 는 것 입 니 다.만족 하면 이러한 하위 문자열 이 존재 한 다 는 것 을 의미한다. 이때 오른쪽으로 이동 하고 두 구역 간 의 하계 로 이동 해 야 한다.만족 하지 않 으 면 왼쪽으로 이동 하고 두 분 구 간 의 상계 로 이동 해 야 한다.height [] 를 처리 하 는 토대 에서 2 분 의 시간 복잡 도 는 O (N * log (N) 이다.
참고 할 만 한 예제 가 있다.http://blog.csdn.net/xj2419174554/article/details/10175343
5. 서로 다른 하위 문자열 의 개수
문자열 을 지정 하여 다른 하위 문자열 의 개 수 를 구하 십시오.
두 문자열 의 가장 긴 공통 문자열
두 문자열 A 와 B 를 지정 하고 가장 긴 공통 문자열 을 구 합 니 다.
따로 토론 하면 폭력 과 동적 계획 이라는 사상 으로 이 문 제 를 풀 수 있다.그러나 시간 복잡 도 는 O (N * N) 로 n 이 많 을 때 는 일반적으로 받 아들 일 수 없다.우 리 는 두 문자열 을 연결 해서 중간 부분 에 두 문자열 에 나타 나 지 않 는 문 자 를 추가 하고 두 문자열 을 분리 할 수 있다.그래서 최 장 공공 문자열 문 제 는 두 구간 에서 시 작 된 두 접미사 의 최 장 공공 접두사 로 바 뀌 었 다.그래서 위 에 있 는 것 으로 바 뀌 었 습 니 다. 시작 위치 만 주의 하 세 요. 하 나 는 왼쪽 에 있 고 하 나 는 오른쪽 에 있 습 니 다.
참고 할 만 한 예제 가 있다.http://blog.csdn.net/xj2419174554/article/details/9973723
다음 며칠 동안 나 는 나의 이 독서 노트 를 자세하게 보완 할 것 이다.
이 글 을 쓸 때 도 이 고인 의 독서 노트 를 참고 하여 함께 감 사 를 드 립 니 다!
http://www.cnblogs.com/staginner/archive/2012/02/02/2335600.html
좋은 웹페이지 즐겨찾기
