OI 완성 계획 - Day 1 접미사 배열

Day1
Part 1,Suffix Array
{어제 늦게 잤 는데 오늘 10 시 에 일 어 났 어 요. 감기 걸 릴 것 같 아 요. 제발 그 러 지 마 세 요! 물 을 죽 어 라 마셔 요..............................................
오늘 은 계획 의 첫날 입 니 다. 주로 전에 배 운 알고리즘 을 복습 하고 자신의 견 해 를 정리 하 러 왔 습 니 다.
Ps: 이 건 알고리즘 강의 원고 가 아 닙 니 다. 알고리즘 을 배우 고 싶 은 사람 은 합숙 팀 의 논문 을 볼 수 있 습 니 다.
모든 알고리즘 중에서 제 가 가장 깊이 이해 한 것 은 접미사 배열 이 라 고 생각 합 니 다. DC3 등 선형 구조 방법 을 모 르 지만 이런 알고리즘 들 은 작성 과 디 버 깅 이 어렵 고 알고리즘 상수 가 많 으 며 실측 속도 의 장점 이 뚜렷 하지 않 습 니 다.(다소 편 파 적 이 라 고 할 수 있 지만 중요 한 것 은 아니다) 따라서 배증 법 으로 구조 방법 을 소개 한다.(그 길 을 잘 아 는 사람 은 분할 선 아래로 바로 뛰 어 내 릴 수 있다)
배가 란 이미 해결 한 범위 가 비교적 작은 문 제 를 통 해 적당 한 방법 을 사용 하여 그 결 과 를 범위 가 비교적 큰 문 제 를 해결 하고 최종 적 으로 문제 의 최종 해 를 얻 을 수 있 도록 하 는 것 이다.문제 풀이 범위 가 배로 늘 어 나 는 경우 가 많 기 때문에 배증 법 이라는 이름 을 얻 었 다.그 응용 이 광범 위 하 다. RMQ 중의 ST 알고리즘, 접미사 배열 의 구조, 그리고 시장 배증 학 등 이다.(멀리 갔 지...)
그리고 접미사 배열 이 사용 하 는 배가 사상 은 내 가 모든 접미사 의 크기 를 비교 하기 어 려 운 이상 접미사 의 이니셜 은 항상 비교 할 수 있다 는 것 이다. 이것 은 우리 에 게 초기 서열 을 줄 것 이다. 이것 은 모든 접미사 가 이니셜 에 따라 배열 한 순서 이다.이니셜 이지 만 접두사 의 접두사 (이하 접두사 로 약칭) 입 니 다. 접두사 의 접 두 사 를 접두사 로 정렬 하 는 것 이 우리 의 임무 입 니 다. 현재 접두사 길이 가 문자열 의 길 이 를 초과 할 때 접두사 의 순서 가 아 닙 니까?우 리 는 두 접 두 사 를 더 긴 접두사 로 연결 함으로써 우리 의 문제 풀이 범 위 를 확대 할 수 있다 는 것 을 알 게 되 었 다.그러나 문 제 는 분 치 사상의 능력 과 같이 우 리 는 문제 의 규 모 를 확대 해 야 할 뿐만 아니 라 문제 풀이 의 규모 도 확대 해 야 한다.
그리고 우 리 는 문자열 S, T (길이 가 같 고 크기 관 계 를 알 고 있 음), A, B (크기 관 계 를 알 고 있 음) 를 발견 하면 S + A, T + B 의 크기 관 계 를 판단 할 수 있 습 니 다.방법 은 매우 간단 하 다. 만약 에 S < > T 가 그렇게 높 은 곳 에서 판결 을 내리 면 S = T 는 A, B 가 두 문자열 의 관 계 를 확정 했다.
이렇게 해서 아까 의 문제 로 돌아 가면 우 리 는 O (1) 의 시간 내 에 비교적 짧 은 접두사 의 관계 로 비교적 긴 접두사 의 관 계 를 확정 할 수 있다.이렇게 하면 전체 접미사 배열 의 구 조 를 완성 할 때 까지 문제 풀이 의 규 모 를 계속 커지 게 한다.
그 다음으로 접미사 배열 의 일부 정 보 를 보조 하여 접미사 배열 을 실제 응용 에 사용 합 니 다. Height 배열 은 각 접미사 와 접미사 배열 의 앞 접미사 의 최 장 공공 접두사 (LCP) 의 길 이 를 일정한 방법 으로 O (n) 시간 안에 완성 할 수 있 습 니 다.방법 은 이미 구 한 두 접미사 의 LCP 에 대해 두 번 째 접미사 의 이니셜 을 제거 하면 새로운 접미사 가 생 긴 다 는 것 이다. 그 전에 (접미사 배열 의 순서) 첫 번 째 접미사 에서 이니셜 을 제거 한 접미사 가 있 을 것 이다. 그러나 그들 이 반드시 인접 한 것 은 아니다.인접 하면 이 접미사 의 Height 는 방금 구 한 LCP 길이 의 1 을 줄 이 는 것 입 니 다.서로 인접 하지 않 으 면 이 접미사 인 Height 가 방금 구 한 LCP 길 이 를 줄 이 고 추가 한 접미사 가 중간 에 삽 입 됩 니 다.이렇게 해서 우 리 는 이미 구 한 해 를 계속 이용 하여 불필요 한 비 교 를 생략 하면 Height 배열 의 구법 을 완성 할 수 있다.
또 하 나 는 임의의 두 접미사 의 LCP (패턴 매 칭 을 제외 하고 하위 문자열 에 대한 통계 문 제 는 대부분 사용 할 수 없 으 며, 패턴 매 칭 은 AC 자동 기 회 를 사용 하 는 것 이 좋 습 니 다) 구법 은 이 두 접미사 사이 의 Height 배열 의 최소 값 (비교적 뚜렷 합 니 다. 누 드 RMQ) 입 니 다.
이상 은 모두 구조 방법 에 대한 학습 노트 입 니 다. 다른 사람의 것 이기 때문에 다음 에 저 는 자신 이 이 를 공부 하고 응용 할 때의 견 해 를 이야기 하고 싶 습 니 다.
우선 패턴 이 일치 합 니 다. 이분법 을 통 해 접두사 배열 에서 패턴 문자열 과 가장 일치 하 는 접 두 사 를 찾 습 니 다. 즉, 접두사 와 패턴 문자열 의 공공 접두사 가 가장 길 고 길이 가 패턴 문자열 의 길이 와 같 으 면 일치 합 니 다. 우 리 는 패턴 문자열 이 모 문자열 에 나타 나 는 횟수 에 관심 이 있다 면 이분법 으로 상하 계 를 확인 할 수 있 습 니 다.마찬가지 로 2 분 검색 과정 에서 많은 비교 가 필요 하지 않 기 때문에 앞에서 언급 한 임의의 두 접미사 의 LCP 로 일치 과정 을 최적화 할 수 있다.
분 야 분 야 분할선
{드디어 포인트 가 왔 습 니 다.. 답답 합 니 다...........................................................................
본 논문 의 중점 은 접미사 배열 의 운용 과 문자열 의 통계 문제 에 있다.상세 분류http://wenku.baidu.com/view/228caa45b307e87101f696a8.html。논문 에서 두 가지 통계 방법 을 언급 했 는데 하 나 는 2 분 의 답 이 고 하 이 라이트 배열 을 접미사 로 나 누 는 것 이 며 다른 하 나 는 단조 로 운 스 택 으로 통 계 를 실현 하 는 것 이다.
나 는 이전에 접미사 나무의 내용 을 본 적 이 있 기 때문에 이 두 가지 방법 은 사실상 접미사 나 무 를 옮 겨 다 니 는 시 뮬 레이 션 이 라 고 생각한다.문자열 에 대한 통계 에 따 르 면 접미사 트 리 는 매우 강력 한 데이터 구조 입 니 다.그것 을 옮 겨 다 니 면 우리 가 원 하 는 모든 정 보 를 얻 을 수 있다.
두 번 째 방법 은 접미사 나 무 를 샅 샅 이 뒤 지 는 것 입 니 다. 스 택 을 이용 하여 시 뮬 레이 션 을 합 니 다.우선 접미사 배열 은 접미사 트 리 가 깊이 에 따라 먼저 옮 겨 다 니 는 순서 로 얻 은 잎 사 귀 노드 이 고 접미사 트 리 에 두 잎 사 귀 노드 가 인접 한 최근 공공 조상 (LCA) 은 접미사 배열 의 Height 배열 임 을 알 수 있다.이렇게 일일이 대응 하 는 관 계 를 맺 으 면우 리 는 접미사 나 무 를 옮 겨 다 니 는 과정 을 모 의 할 수 있다.먼저 첫 번 째 접 두 사 를 창고 에 넣 으 세 요. 이것 은 접두사 나무 가 첫 번 째 잎 노드 까지 옮 겨 다 니 는 것 과 같 습 니 다.그 다음 에 중요 한 것 은 접미사 트 리 를 옮 겨 다 닐 때 거 슬러 올 라 가 는 과정 을 모 의 하 는 것 입 니 다. 우 리 는 Height 배열 을 통 해 현재 스 택 꼭대기 노드 를 제어 하여 접 두 사 를 옮 겨 다 니 지 않 은 다음 아버지 결점 으로 만 듭 니 다. 즉, 매번 다음 방문 을 위해 준비 합 니 다 (구체 적 으로 문 말 프로그램 참조). 이렇게 하면 전체 접미사 트 리 를 옮 겨 다 닐 때 까지 모 의 합 니 다.한편, 우 리 는 옮 겨 다 니 는 동시에 접미사 트 리 에 해당 하 는 노드 의 정 보 를 얻 을 수 있 습 니 다. 그 중에서 접미사 의 최대 시작 위치, 각 접미사 가 나타 나 는 횟수 등 모든 정 보 를 저장 합 니 다.이 정 보 는 모두 하위 노드 의 정보 가 합 쳐 질 수 있다.이렇게 하면 O (n) 시간 안에 우리 가 원 하 는 모든 정 보 를 얻 고 문 제 를 신속하게 해결 할 수 있다.
그러나 문제 가 또 발생 했다. 접미사 나무의 효율 은 노드 정 보 를 신속하게 합병 할 수 있 는 토대 위 에 세 워 진 것 이다.만약 에 노드 정 보 를 합병 하 는 시간 복잡 도가 O (1) 를 초과 하면 옮 겨 다 니 는 시간 복잡 도가 O (n) 를 초과 하여 문 제 를 효율 적 으로 해결 하지 못 한다.이런 합병 하기 어 려 운 정보 가 있 을 까?답 은 긍정 적 입 니 다. 사실 이곳 의 통합 노드 정보 와 선분 트 리 는 비슷 합 니 다. 선분 트 리 는 이 선분 안에 몇 가지 다른 색 이 있 는 지 유지 하기 어렵 습 니 다. 접미사 트 리 에 대응 하 는 것 은 하위 트 리 에 몇 가지 서로 다른 문자열 에 속 하 는 접미사 입 니까?문자열 이 적 을 때 집합 이나 비트 연산 으로 이 루어 지 는 것 을 고려 할 수 있 지만 문자열 이 매우 많 을 때 (1000 이상) 합병 시간 이 크게 증가한다.우 리 는 당연히 많은 숫자 로 집합 (똑 같이 비트 연산) 을 표시 할 수 있 지만 이런 속 도 는 최적화 되 었 지만 프로 그래 밍 의 복잡 도 는 더욱 증가 하여 얻 는 것 보다 잃 는 것 이 많 을 수 있다.이것 은 우리 가 다른 측면 에서 문 제 를 생각 하도록 일 깨 워 야 한다. 우리 가 서브 노드 의 정 보 를 합병 하기 어 려 운 이상 이 노드 에 포 함 된 접미사 로 본 노드 의 정 보 를 직접 업데이트 하지 않 는 것 이 어 떨 까?이것 이 바로 방금 언급 한 첫 번 째 방법 이다.
첫 번 째 방법 은 접미사 트 리 를 층 별로 옮 겨 다 니 는 것 으로 광 수 와 유사 하 다.그러나 접미사 트 리 의 모든 노드 를 하위 트 리 의 잎 노드 로 직접 업데이트 하면 시간 복잡 도 는 O (Hn) 에 도착 합 니 다.(H 는 전체 접미사 나무의 높이) 역시 시간 을 초과 하 는 곤경 에 직면 할 것 이다.우리 가 만난 이런 문 제 는 대부분 가장 가치 있 는 문 제 를 해결 하 는 등 최 적 화 된 문제 이다.그러면 우 리 는 현재 층 의 정 보 를 통 해 가장 좋 은 해 가 현재 층 의 위 에 있 는 지 아래 에 있 는 지 판단 할 수 있다. 그러면 2 분 의 빠 른 포 지 셔 닝 을 통 해 우리 가 찾 아야 할 노드 를 통 해 문 제 를 해결 할 수 있다.그것 의 장점 은 O (n) 시간 내 에 현재 층 노드 의 정 보 를 계산 할 수 있 고 부합 되면 아래 층 의 노드 가 부합 되 는 지, 부합 되 지 않 으 면 위로 우리 의 문 제 를 해결 할 때 까지 볼 수 있다 는 것 이다.시간 복잡 도 총 O (nlogH).만약 에 시간 이 비교적 여유 가 있다 면 우 리 는 이 방법 으로 경로 없 이 압축 된 접미사 트 리 에서 할 수 있다. 프로 그래 밍 의 복잡 도 는 더욱 떨 어 지고 시간 복잡 도 는 O (nlogn) 이다. 즉, 논문 에서 언급 한 2 분 의 답 방법 으로 Height 배열 에 그룹 을 나 누 는 것 이다.
물론 이것 은 모든 문자열 통계 의 문 제 를 완벽 하 게 해결 하지 못 했다. 예 를 들 어 문제 에서 N 개의 문자열 을 구 해 야 한다. 길이 가 k 보다 작 지 않 은 서로 다른 공공 하위 문자열 의 개 수 는 두 개의 공공 하위 문자열 이 같 고 모든 문자열 에 나타 난 위치 만 같다. 즉, N = 2 일 때 이다.
AABBAABBA 와 ABBAABBB 가 다른 공공 하위 꼬치 ABB 는 모두 4 개다.
(색상 이 다른 ABB 는 자 유 롭 게 조합 할 수 있 습 니 다.) 표현 이 잘 모 를 수도 있 습 니 다. 자세 한 내용 은 POJ 3415 를 참조 할 수 있 습 니 다. 이 문제 의 간략화 판 은 두 개의 문자열 만 있 습 니 다.
그럼...분명 한 것 은 첫 번 째 방법 은 사용 할 수 없다 (최적화 되 지 않 았 기 때문에 이분 성 이 없다). 두 번 째 방법 은 서브 노드 의 정 보 를 합병 하기 어렵 고 문 제 를 곤경 에 빠 뜨 린 다.
사실 이렇게 슬퍼 할 필요 가 없습니다. 만약 에 제목 의 N 이 크 면 모든 문자열 의 길이 가 너무 크 지 않 습 니 다. 만약 에 둘 다 크 면 모든 문자열 을 연결 한 후에 길이 가 너무 길 고 O (n) 는 접미사 배열 의 구 조 를 실현 하기 어렵 기 때 문 입 니 다.이때 접미사 트 리 의 높이 가 작 을 수 있 으 므 로 O (H * len) (len 은 접미사 배열 의 길이) 방법 으로 시도 해 볼 수 있 습 니 다.N 이 작 으 면 단조 로 운 스 택 방법 도 해 볼 만하 다.그러나 이것 은 결국 제목 이 접미사 배열 로 풀 리 는 조건 에서 더 좋 은 방법 이 있 을 지도 모 르 지만 이것 은 내 가 현재 가지 고 있 는 수준 을 넘 어서 더 이상 토론 하지 않 는 다.
Ps: 표 현 력 이 매우 떨 어 지 니 여러분 들 은 아 쉬 운 대로 보 세 요.
[여러분 이 문장의 부족 함 을 지적 한 것 을 환영 합 니 다. 우 리 는 다시 진일보 한 토론 을 하 겠 습 니 다. 만약 잘못 이 있 으 면 제 가 제때에 수정 하 겠 습 니 다.]
[Snow Dancer 오리지널, 옮 겨 실 을 때 밝 혀 주세요. 감사합니다.]

  1 {POJ3415,        }
  2 var
  3   s,sa,sap,num:array[0..200010] of longint;
  4   r:array[0..1,0..200010] of longint;
  5   stack:array[0..200010] of record a,b,h:int64;end;
  6   height:array[0..200010] of int64;
  7   n,i,j,k,l,size,x,y,di,top,limit:longint;
  8   ans:int64;
  9   c:char;
 10 function max(x,y:int64):int64;
 11   begin if xthen exit(y) else exit(x); end;
 12 procedure BuildSA;//      
 13   begin
 14     size:=255;
 15     for i:=1 to size do num[i]:=0;
 16     for i:=1 to n do inc(num[s[i]]);
 17     for i:=1 to size do inc(num[i],num[i-1]);
 18     r[1]:=s;
 19     for i:=n downto 1 do begin
 20       sa[num[s[i]]]:=i;dec(num[s[i]]);
 21     end;
 22     k:=1; x:=1;y:=0;
 23     repeat
 24       for l:=1 to k do sap[l]:=n-l+1;
 25       for i:=1 to n do
 26         if sa[i]>k then begin
 27           inc(l);sap[l]:=sa[i]-k;
 28         end;
 29       for i:=1 to size do num[i]:=0;
 30       for i:=1 to n do inc(num[r[x,sap[i]]]);
 31       for i:=2 to size do inc(num[i],num[i-1]);
 32       for i:=n downto k do begin
 33         sa[num[r[x,sap[i]]]]:=sap[i];dec(num[r[x,sap[i]]]);
 34       end;
 35       size:=0;
 36       for i:=1 to n do begin
 37         if not ((r[x,sa[i]]=r[x,sa[i-1]])and(r[x,sa[i]+k]=r[x,sa[i-1]+k])) then inc(size);
 38         r[y,sa[i]]:=size;
 39       end;
 40       x:=y;y:=y xor 1;k:=k<<1;
 41     until (k>=n)or(size=n);
 42   end;
 43 procedure calheight;//  Height  
 44   begin
 45     k:=0;
 46     for i:=1 to n do begin
 47       if k>0 then dec(k);j:=sa[r[x,i]-1];
 48       while s[i+k]=s[j+k] do inc(k);
 49       height[r[x,i]]:=k;
 50     end;
 51   end;
 52 procedure Traversal;    //      
 53   procedure push(k:longint);
 54     begin
 55       if height[k+1]>stack[top].h then begin
 56         inc(top);
 57         stack[top].h:=height[k+1];
 58         stack[top].a:=0;
 59         stack[top].b:=0;
 60       end;
 61       if sa[k]then
 62         inc(stack[top].a)     //              
 63       else
 64         inc(stack[top].b);
 65     end;
 66   procedure pop(k:longint);
 67     begin
 68       if stack[top].hthen begin dec(top);exit;end;
 69       if height[k+1]<=stack[top-1].h then begin
 70         inc(ans,stack[top].a*stack[top].b*(stack[top].h-max(limit-1,stack[top-1].h)));
 71         inc(stack[top-1].a,stack[top].a);
 72         inc(stack[top-1].b,stack[top].b);
 73         dec(top);
 74       end else begin
 75         inc(ans,stack[top].a*stack[top].b*(stack[top].h-max(height[k+1],limit-1)));
 76         stack[top].h:=height[k+1];
 77       end;
 78     end;
 79   begin
 80     for i:=1 to n do begin
 81       push(i);
 82       while stack[top].h>height[i+1] do pop(i);
 83     end;
 84   end;
 85 begin
 86   readln(limit);
 87   while limit<>0 do begin
 88     n:=0; ans:=0; top:=0;
 89     fillchar(height,sizeof(height),0);
 90     fillchar(num,sizeof(num),0);
 91     fillchar(sa,sizeof(sa),0);
 92     fillchar(sap,sizeof(sap),0);
 93     fillchar(s,sizeof(s),0);
 94     fillchar(r,sizeof(r),0);
 95     while not eoln do begin
 96       read(c);inc(n);s[n]:=ord(c);
 97     end;readln;
 98     inc(n);s[n]:=124;di:=n;
 99     while not eoln do begin
100       read(c);inc(n);s[n]:=ord(c);
101     end;readln;
102     BuildSA;
103     calheight;
104     Traversal;
105     writeln(ans);
106     readln(limit);
107   end;
108 end.

 
다음으로 전송:https://www.cnblogs.com/Snow-Dancer/archive/2012/07/01/2572352.html