[문자열 데이터 구조 접미사 시리즈 Part 1] 접미사 배열 학습 노트

AC 자동 동기 대단 하 다 ww 그래서 나 는 접미사 자동 동기 와 접미사 배열 을 배 워 야 겠 다.
- - - - - - - 선 분할 은 나 > w 방법 에 따라 문자열 일치 알고리즘 / 데이터 구 조 는 접두사 와 접두사 두 가지 로 나 뉜 다. 접 두 사 는 AC 자동 동기 로 KMP 와 Trie 가 가장 유명 하 다. 접 두 사 는 접두사 자동 동기 / 접두사 배열 / 접두사 트 리 가 대표 적 이다. 나 는 접 두 사 를 배 우 는 것 이 니 네가 나 를 물 어 라 ww
먼저 몇 가지 정 의 를 내 립 니 다 ~ (≥ ≤) / ~ 1. 보통 우 리 는 ← 로 하나의 문자 집합 (모든 요 소 는 하나의 문자) 을 표시 합 니 다. 그 중에서 모든 문 자 는 서로 다 르 고 그 중의 문자 두 개 사이 에 크기 를 비교 할 수 있 습 니 다. 둘째, 문자열 은 ＞ 중의 몇 개의 문자 가 일정한 순서에 따라 배열 하여 형 성 된 배열 입 니 다. 길 이 는 n 인 문자열 s 이 고 그 길 이 는 len (s) 으로 기록 합 니 다.문자열 S 의 i 번 째 문 자 는 s [i] 로 기록 합 니 다. 3. 문자열 s 의 i 번 째 부터 j 번 째 까지 의 연속 문자 로 구 성 된 문자열 을 s 의 키 문자열 이 라 고 합 니 다. 주의 하 세 요. 빈 문자열 도 s 의 키 문자열 입 니 다. 4. s 의 i 번 째 를 선택 하면 첫 번 째 부터 i 번 째 까지 의 하위 문자열 을 s 의 접두사 라 고 합 니 다. 해당 하 는 i 번 째 부터 n 번 째 로 구 성 된 하위 문자열 을 s 의 접두사 라 고 합 니 다. 5. 사전 순서 비교 원칙,두 꼬치 s1, s2 의 첫 번 째 부터 하나씩 뒤로 비교 합 니 다. 만약 에 하나의 문자 s1 [i] > s2 [i] 가 존재 한다 면 s1 사전 순서 가 꼬치 s2 보다 크 고 s1 [i] < s2 [i] 는 s1 < s2;두 꼬치 중 한 꼬치 의 마지막 자 리 를 쓸 어 버 릴 때 까지 비교 결 과 를 얻 지 못 하면 길이 에 따라 렌 (s1) < 렌 (s2), s1 < s2 를 비교 합 니 다.그렇지 않 으 면 balabala = = 한 문자열 의 모든 접미사 에 대해 사전 순서 가 같 을 수 없 음 이 분명 합 니 다. 이것 도 접미사 데이터 구 조 를 사용 하 는 중요 한 조건 입 니 다.
기본 지식 이 끝나 면 접미사 배열 을 시작 해 야 합 니 다 = - = 접미사 배열: 우 리 는 먼저 문자열 의 모든 접 두 사 를 사전 순서에 따라 작은 것 부터 큰 것 까지 정렬 한 다음 에 sa 라 는 배열 을 만 듭 니 다. sa [i] 는 정렬 후 i 번 째 문자열 이 표시 하 는 접 두 사 는 원래 문자열 s 의 몇 번 째 부분 에서 시 작 됩 니 다. 우 리 는 Suffix [i] 로 i 번 째 접두사 를 표시 하면 분명 합 니 다.
Suffix[sa[i]]접미사 배열 은 혼자 나타 나 지 않 고 석차 배열 을 동시에 사용 합 니 다.
석차 배열: 석차 배열 rank 을 정의 하면 rank [i] 는 원래 문자열 에서 i 위 부터 기 록 된 접 두 사 를 모든 접미사 에서 사전 순 서 를 어 릴 때 부터 얼마나 줄 지어 있 는 지 나타 낸다.
그래서 접미사 배열 sa 와 rank 은 사실은 한 쌍 의 상호 역 연산 이다.
어떻게 서로 거 스 릅 니까?SA [i] = j 가 있 으 면 Rank [j] = i
그래서 이 두 배열 은 우리 가 임 의 하 나 를 구하 면 된다.
O (n) 의 다른 것 을 구하 세 요.
그럼 문제 가 생 겼 습 니 다. 접미사 배열 을 어떻게 구성 합 니까?분명히 가장 누 드 한 사 고 는 모든 접 두 사 를 만 들 고 정렬 을 시 킨 다음 에 하 는 것 이다. logn) 이렇게 느 리 면 어떻게 하 시 겠 습 니까?
두 배 확장 접미사 배열: 문자열 s 의 한 분 한 분 을 시작 으로 한 분 부터 길이 가 2k 인 하위 문자열 을 가 져 와 하위 문자열 을 정렬 하고 rank 을 구 합 니 다. 하위 문자열 이 충분히 길 면 이 하위 문자열 은 전체 문자열 의 접미사 가 되 어 전체 rank 배열 을 구 할 수 있 습 니 다. 따라서 배가 될 때 우 리 는 모든 문자열 을 다시 꺼 낼 필요 가 없습니다.이전의 rank 의 공헌 은 여전히 보류 할 수 있 기 때문에 새로 배 증 된 2k − 1 의 하위 문자열 의 rank (두 개의 2k − 1 꼬치 의 rank 를 모두 기록 해 야 함) 를 이용 하면 2k 문자열 의 rank 를 얻 을 수 있 습 니 다. 속 도 를 내기 위해 서 는 기수 로 정렬 합 니 다 (물론 대기 문자열 이 매우 크 면 빨리 배열 할 수 밖 에 없습니다). 따라서 전체 복잡 도 는 O (nlogn) 입 니 다.(빨리 줄 을 서 려 면 log 가 하나 더 필요 합 니 다)
다음은 시원 한 코드 를 체험 해 보 겠 습 니 다. 접미사 배열 을 구축 하 는 코드 를 본 사람 이 많 을 거 라 고 믿 습 니 다. 그 10 여 개의 지저분 한 for 는 정말 사람 을 아 프 게 합 니 다.
막 나 수 건 논문. 논문 에서 코드 작성 법 은 여러 가지 측면 에서 유 여 가 의 훈련 지침 작성 법 보다 우수 하 다.

#include
using namespace std;
#define MAXN 100010
char s[MAXN];
int A[MAXN];
//        ,   s         .s A       0-n-1 
int sa[MAXN],rank[MAXN];//     rank sa
int Count[MAXN];//        
int l[MAXN],r[MAXN],tmp[MAXN];//           ,r            ,l    rank . 
int n,maxn;//     
bool comp(int *A,int a,int b,int len)//      
{
    return A[a]==A[b]&&A[a+len]==A[b+len];
}
int main()
{
    /*          */
    int i,j,k,*x=l,*y=r;//       l,r         
    for (i=0;i0;
    for (i=0;i//        
    for (i=1;i1];
    for (i=n-1;i>=0;i--)    sa[--Count[x[i]]]=i;//   sa 
    for (k=1,i=1;i1,maxn=i)
    {
        for (i=0,j=n-i;j//       
        for (j=0;jif (sa[j]>=k)   y[i++]=sa[j]-k;
        for (j=0;jfor (j=0;j0;
        for (j=0;jfor (j=1;j1];
        for (j=n-1;j>=0;j--)    sa[--Count[tmp[j]]]=y[j];//  sa 
        for (swap(x,y),i=1,x[sa[0]]=0,j=1;j1],sa[j],k)?i-1:i++;//  rank
        //             rank   ,                 rank 
        //  y        sa     (       ),      y  rank 
    }
}

SA 애플 리 케 이 션 은 SAM 에 이 어 블 로그 를 따로 쓰 려 고 합 니 다.