[코드모음] - 문자열

/* KMP */

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) {  //z=pi[pi[i-1]] + 1 로 표현하는게 핵심

                                   pi[i] = 0;

                                   break;

                           }

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

                  }

         } 

 

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) { //찾음

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

                           Rcnt++;

                           R[Rcnt] = i - M + 1;

                           k = pi[k];

                  }

                  k++;

         }

 

/* 허프만 코드 */

1. 각 문자에 대한 빈도 수 계산해서 큐(min_heap)에 넣는다.

        for (i = 1; i <= 26; i++)     cnt[i] = 0;

        for (i = 1; i <= n; i++)      cnt[A[i] - 'A' + 1]++;

        for (i = 1; i <= 26; i++)     if (cnt[i] != 0)       q.push(make_pair(cnt[i], i));

2. 큐의 상위 두 개(가장 작은값 두 개)를 꺼내고, 이 두 개의 합을 값으로하는 tree node 생성하고, 이 값을 큐에 push. 큐 크기가 2보다 작아질때까지 루프

        for (i = 1; i<100; i++)       tree[i].clear();

        treeCnt = 26;

        while (q.size() >= 2){

               t1 = q.top(); q.pop();

               t2 = q.top(); q.pop();

               tree[++treeCnt].push_back(t1.second); //트리 왼쪽

               tree[treeCnt].push_back(t2.second);   //트리 오른쪽

               q.push(make_pair(t1.first+t2.first, treeCnt));              

        }

3. 큐에 남아있는 값(트리의 루트값임)을 출발점으로해서 DFS를 돌면서, 이진값 계산

dfs(q.top().second, 0);

void dfs(int curr, int lev){     

                if (tree[curr].empty())               bits[curr] = lev;     

                else{

                       for (int i = 0; i<tree[curr].size(); i++)    dfs(tree[curr][i], lev + 1);

                }

}

 

* 소스

void dfs(int curr, int lev){ 

        if (tree[curr].empty())               bits[curr] = lev;     

        else{

               for (int i = 0; i<tree[curr].size(); i++)    dfs(tree[curr][i], lev + 1);

        }

}

void process(void){

        int i;

        priority_queue<ppair, vector<ppair >, greater<ppair > > q;

        ppair t1, t2, tt;

 

        for (i = 1; i <= 26; i++)     cnt[i] = 0;

        for (i = 1; i <= n; i++)      cnt[A[i] - 'A' + 1]++;

        for (i = 1; i <= 26; i++)     if (cnt[i] != 0)       q.push(make_pair(cnt[i], i));

       

        for (i = 1; i<100; i++)       tree[i].clear();

        treeCnt = 26;

        while (q.size() >= 2){

               t1 = q.top(); q.pop();

               t2 = q.top(); q.pop();

               tree[++treeCnt].push_back(t1.second);

               tree[treeCnt].push_back(t2.second);

               q.push(make_pair(t1.first+t2.first, treeCnt));              

        }

        dfs(q.top().second, 0);

        q.pop();

}

void output(void){

        int i, answer = 0;

        for (i = 1; i <= n; i++){

               answer += bits[A[i] - 'A' + 1];

        }

        fprintf(fp2, "%d\n", answer);

}

-끝-