[문자열]

1. 접미사 배열

2. KMP

----------------------------

1. 접미사 배열

- 한 문자열에서, 나올 수 있는 모든 가능성 있는 접미사를 사전순으로 정렬해 놓은 배열

- 큰 문장이 있을 때 '찾기' 기능 구현에 적합. <- 찾으려는 문자열은, 항상 접미사 배열의 접두사

- 접미사배열을 만드는 데는, 일반적인 소팅을 하면 O(N²longN) : 소팅하는데 NlongN. 그리고 각 소팅마다 문자열 비교하는데 N

char str[1005]

string suffix[1005]

scanf("%s",A+1)

for(int i=1;i<=n;++i) suffix[i] = &str[i];

sort(suffix+1, suffix+n+1)

- 가장 빠른 알고리즘은 O(N)가능-> 너무 복잡. 

- 맨버 마이어스 알고리즘을 쓰면 O(Nlg²N) 가능

2. KMP

- pi[] 테이블 만들고, 이 테이블을 이용해서 문자열 매칭을 효율적으로 수행

*문자열 A에서, B문자열이 들어있는지 찾아내려함.

         scanf("%s", A + 1);

         scanf("%s", B + 1);

 

         N = strlen(A + 1);

         M = strlen(B + 1); 

1)pi 테이블 만들기

         pi[1] = 0;

         for (int i = 2; i <= M; i++) {

                  pi[i] = pi[i - 1] + 1;

                  while (true) {

                           if (B[pi[i]] == B[i]) { //같으면, pi[i] = pi[i - 1] + 1 가 그대로 유지

                                   break;

                           }

                           if (pi[i] == pi[pi[i - 1]] + 1) {  //pi[pi[i-1]] + 1 로 표현하는게 핵심

                                   pi[i] = 0;

                                   break;

                           }

                           pi[i] = pi[pi[i - 1]] + 1;

                  }

         } 

2)테이블 이용해서 문자열 매칭 찾아내기

   int k = 1;

         for (int i = 1; i <= N; i++) {

                  while (k > 0 && A[i] != B[k]) {

                           if (k == 1) {

                                   k = 0;

                                   break;

                           }

                           k = pi[k - 1] + 1; //같지 않은 부분을 만나면, k를 pi[k-1]+1 으로 이동.

                  }

                  if (k == M) { //찾음

                           Rcnt++;

                           R[Rcnt] = i - M + 1; //현재 찾아낸 위치 i는, 원래 문자열에서 M문자열만큼 움직인 상태이기에, i-M+1 해줌

                           k = pi[k];

                  }

                  k++;

         }

-끝-