문자열 알고리즘

1. 개요

2. 문자열 검색 알고리즘

2.1. Naïve String Search

2.1.1. 코드

#!syntax cpp
#include <iostream>
#include <string>

using namespace std;

void find_pattern(const string &, const string &);

int main(const int argc, const char **argv)
{
    const string haystack = "hello hello hello hellchosun";
    const string needle = "hell";

    find_pattern(haystack, needle);

    return 0;
}

void find_pattern(const string &haystack, const string &needle)
{
    const auto haystack_size = haystack.size();
    const auto needle_size = needle.size();
    size_t i;
    size_t j;
    bool unmatched_flag = true;

    cout << "Begin to find pattern \"" << needle << "\" at target string \"" << haystack << "\"" << endl;

    for (int i = 0; i < haystack_size - needle_size; ++i)
    {
        for (int j = 0; j < needle_size; ++j)
        {
            if (haystack[i + j] == needle[j])
            {
                continue;
            }

            break;
        }

        if (j == needle_size)
        {
            cout << "Pattern \"" << needle << "\" matched at " << i + 1 << " ~ " << i + 1 + needle_size << endl;

            unmatched_flag = false;
        }
    }

    if (unmatched_flag)
    {
        cout << "Pattern unmatched" << endl;
    }
}

2.2. Finite-state automaton based search

2.3. Knuth-Morris-Pratt Algorithm

• "abcdabckl"이라는 문자열이 있다고 하자. 이때 i = -1, j = 0이며, 시작 위치의 상태함수에 들어갈 값은 -1이다.
• i와 j를 한 칸씩 전진시킨 뒤 비교한다.
• i와 j가 매치되면 혹은 i == -1일 때 한칸씩 전진한 뒤, j 위치에 i를 저장한다.
• 만약 i와 j가 매치되지 않는다면 i는 상태전이함수에 있는 값으로 전환시킨 뒤 2로 돌아간다.
• j가 n보다 커질 때까지 반복한다.
• 이 과정을 거친 상태전이함수는 0 0 0 0 1 2 3 0 0이 된다.

2.3.1. 코드

#!syntax cpp 
//상태전이함수 생성
void kmp(char *pat) {
    int n = strlen(pat);
    int i = -1, j = 0;
    pi[j] = i;
    while(j < n) {
        if(i == -1 || pat[i] == pat[j])
            pi[++j] = ++i;
        else 
            i = pi[i];
    }
}

//문자열 비교
void find_pattern(char *arr, char *pat) {
    int n = strlen(arr);
    int m = strlen(pat);
    int i = j = 0;
    while(i < n) {
        if(j == -1 || arr[i] == pat[j]) 
            i++, j++;
        else
            j = pi[j];
        
        if(j == m) {
            printf("The matching %d\n",i-m+1);
            j = pi[j];
        }
    }
}

2.4. Rabin-Karp string search algorithm

2.4.1. 코드

#!syntax cpp
#define mod 1000000009
long long make_hash_p(char str[], int _size) {
	int i;
	long long hash_p = 0;
	for (i = 0; i < _size; i++) {
		hash_p *= 26;
		hash_p += str[i];
		hash_p %= mod;
	}
	return hash_p;
}
void match_s(char str[], int _size, int _size_p, long long hash_p) {
	int i;
	long long hash_s = 0;
	long long last = 1;
	for (i = 0; i < _size_p; i++) {
		hash_s *= 26;
		hash_s += str[i];
		hash_s %= mod;

		if (i == _size_p - 1) continue;
		last *= 26;
		last %= mod;
	}
	for (i = _size_p; i <= _size; i++) {
		if (i >= _size_p) {
			if (hash_s == hash_p) printf("match %d\n", i - _size_p + 1);
			if (i == _size) break;

			hash_s -= last * str[i - _size_p];
			hash_s *= 26;
			hash_s += str[i];
			hash_s %= mod;
			if (hash_s < 0) hash_s += mod; //빼는 과정에서 해시값이 음수가 되는 경우를 방지
		}
	}
}

3. 최장 공통 부분 문자열(Longest Common Substring)

3.1. Dynamic Programming

1. 다음 식에 의해서 표를 생성한다.
• 0 ≤ i ≤ len(A)이고 0 ≤ j ≤ len(B)일 때,
• A[i] == B[j]일 경우 LCSTable(i, j) = LCSTable(i - 1, j - 1) + 1
• 아닐 경우 LCSTable(i, j) = 0
2. 표에서 가장 큰 숫자를 확인한다.
• A = BCBBBC, B = CBBBCC 인 경우

3.1.1. 코드

#!syntax cpp
void find() {
    int i, j;
    int max1 = 0, tmpi = 0;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(s[i - 1] == p[j - 1]) dt[i][j] = dt[i - 1][j - 1] + 1;
            if(dt[i][j] > max1) {
                max1 = dt[i][j];
                tmpi = i;
            }
        }
    }
    printf("%d\n", max1);
    while(max1--) {
        ans[max1] = s[tmpi-1];
        tmpi--;
    }
    printf("%s", ans);
}

3.2. Suffix Array + LCP Array

3.2.1. 코드

#!syntax cpp
//Suffix Array 및 LCP Array 생성
bool cmp(int a, int b) {
    if (o[a] != o[b]) return o[a] < o[b];
    int x = a + gap;
    int y = b + gap;
    return ((x < n && y < n) ? o[x] < o[y] : x > y);
}
void makeSA() {
    int i;
    for (i = 0; i < n; i++) o[i] = s[i] - 'a', sa[i] = i;
    for (gap = 1;; gap < 1) {
        sort(sa, sa + n, cmp);
        tmp[0] = 0;
        for (i = 0; i < n - 1; i++) tmp[i + 1] = tmp[i] + cmp(sa[i], sa[i + 1]);
        if (tmp[n - 1] == n - 1) break;
        for (i = 0; i < n; i++) o[sa[i]] = tmp[i];
    }
}
void makeLCP() {
    int i, j;
    int k = 0;
    for (i = 0; i < n; i++) Rank[sa[i]] = i;
    for (i = 0; i < n; lcp[Rank[i++]] = k) {
        for ((k ? k-- : 0), j = (Rank[i] ? sa[Rank[i] - 1] : n); i + k < n && j + k < n && s[i + k] == s[j + k]; k++);
    }
}

int find() {
    int i;
    int max1 = 0, d;
    int h, t;
    bool sw = false;
    for (i = 0; i < n; i++) {
        if (sa[i] >= n - m) {
            t = 0x7fffffff;
            sw = true;
        } else if (sw) {
            h = n - sa[i] < lcp[i] ? n - sa[i] : lcp[i];
            t = t < h ? t : h;
            if (max1 < t) {
                max1 = t;
                d = sa[i];
            }
        }
    }
    sw = false;
    for (i = 0; i < n; i++) {
        if (sa[i] < n - m) {
            t = 0x7fffffff;
            sw = true;
        } else if (sw) {
            h = n - sa[i] < lcp[i] ? n - sa[i] : lcp[i];
            t = t < h ? t : h;
            if (max1 < t) {
                max1 = t;
                d = sa[i];
            }
        }
    }
    printf("%d\n", max1);
    for (i = d; i < d + max1; i++) printf("%c", s[i]);
    return 0;
}

4. 다중 패턴 매칭

4.1. Aho-Corasick Algorithm

4.1.1. 코드

#!syntax cpp
struct node {
    int i;
    int j;
};
queue<node> q;
// failure function 생성
void make_fail(int trie[][26], int fail[], bool chk[]) { // trie - 트라이, fail - 상태전이 함수, chk - 문자열 존재 여부
        node tmp, now; // now = 현재 위치를 담는 node, tmp = 보조 node (갱신 등)
        tmp.i = -1;
        tmp.j = 0;
        q.push(tmp);
        while (q.size()) {
            now = q.front();
            q.pop();
            for (k = 0; k < 26; k++) {
                tmp = now;
                if (trie[tmp.j][k] == 0) continue; // j에 대해 다음 노드로 이동 할 수 없다면 
                while (1) {
                    if (tmp.i == -1 || (tmp.i != -1 && trie[tmp.i][k] > 0)) { // i에 대해 다음 노드로 이동 가능하거나, failure function을 사용할 수 없다면
                        if (tmp.i == -1) tmp.i = 0;
                        else tmp.i = trie[tmp.i][k];
                        tmp.j = trie[tmp.j][k];
                        fail[tmp.j] = tmp.i;
                        if (chk[tmp.i] == true) chk[tmp.j] = true;
                        q.push(tmp);
                        break;
                    }
                    else tmp.i = fail[tmp.i]; // i에 대해 다음노드로 이동이 불가능 하고, failure function을 사용할 수 있다면
                }
            }
       }
}
bool match(char s[], int tire[][26], int chk[]) { //문자열 s
        int i = 0, j = 0;
        while (1) {
            if (j == n) break;
            nxt = s[j] - 'a'; // 다음 상태로 이동하기 위한 문자 nxt
            if (i == -1 || (i != -1 && trie[i][nxt] > 0)) { // i가 더 이상 failure fuction을 방문하지 못하게 되거나, 혹은 다음 상태로 이동이 가능하면
                if (i == -1) i = 0;
                else i = trie[i][nxt];
                j++;
            }
            else i = fail[i]; // i가 failure function을 방문 가능하며, 다음 상태로 이동 불가능할때
            if (i != -1 && chk[i]) return true;
        }
        return false;
}