[C++] 문자열

문자열

1. KMP 알고리즘

문자열 검색을 빠르게 구하기 위한 알고리즘이다.

 

1) 기본 원리

접두사(prefix)와 접미사(suffix)를 이용해 pi[i] 배열을 구한 뒤 활용한다. pi[i] 배열은 0~i까지의 부분 문자열에서 prefix=suffix가 될 수 있는 부분 문자열 중 가장 긴 것의 길이이다. 이때, prefix가 0~i까지의 부분 문자열과 같으면 안 된다.

 

예를 들어 문자열 ABAABAB로 pi[i] 배열을 구해보자.

 

i	부분 문자열 (0~i)	pi[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

 

그렇다면 이 pi[i] 배열을 어떻게 활용하여 문자열 검색을 효율적으로 할 것인가?

 

문자열 ABCDABCDABEE에서 문자열 ABCDABE를 찾는 상황을 가정해보자. 아래와 같은 상황에서 문자열 매치에 실패했을 때, 기존 문자열 검색은 인덱스 1로 이동해 검색을 진행한다.

 

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A

B

C

D

A

B

E

E

패턴

A

B

C

D

A

B

E

 

그러나, pi[i] 배열을 사용한다면 현재 두 문자열이 일치하는 부분 문자열은 ABCDAB(0~5)이고 pi[5]=2이므로 이미 문자열 AB가 일치한다는 것을 알 수 있어 인덱스 1이 아닌 인덱스 4로 넘어가 검색을 진행할 수 있다.

 

2) 문제

https://www.acmicpc.net/problem/1786

1786번: 찾기

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> kmp(string T, string P)
{
    vector<int> answer;
    int n = T.size(), m = P.size();

    // pi[i] 배열 구현
    vector<int> pi(m, 0);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && P[i] != P[j])
            j = pi[j - 1];
        if (P[i] == P[j])
            pi[i] = ++j;
    }

    // kmp 함수 구현
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && T[i] != P[j])
            j = pi[j - 1];
        if (T[i] == P[j]) {
            if (j == m - 1) {
                answer.push_back(i - m + 2);
                j = pi[j];
            }
            else {
                j++;
            }
        }
    }

    return answer;
}

int main()
{
    string T, P;
    getline(cin, T);
    getline(cin, P);

    vector<int> answer = kmp(T, P);
    cout << answer.size() << "\n";
    for (auto i : answer)
        cout << i << "\n";
}

 

2. 라빈 카프 알고리즘(Rabin-Karp Algorithm)

문자열 검색을 빠르게 구하기 위한 알고리즘이다.

 

1) 기본 원리

해싱에 기반한다. 문자열 내 모든 위치에서 비교하는데, 먼저 해당 위치의 해시값을 비교하고 같다면 그제야 단순 비교를 한다. 해시 함수를 잘 구현해서 충돌이 적은 해시 함수를 만든다면 유용한 알고리즘이 될 것이다.

 

가장 많이 사용되는 해시 함수는 Rabin fingerprint로 아래와 같은 형태를 갖고 있다.

• T[i]: 해당 문자의 아스키코드를 사용하면 된다.

H(i) = T[i] *2^(M-1)+ T[i+1] * 2^(M-2)+ ... + T[i+M-2]*2^(1) + T[i+M-1]*2^(0)
H(i) = 2 * (H(i-1) - T[i - 1] * 2^(M-1)) + T[i+M-1] (점화식)

 

2) 문제

https://www.acmicpc.net/problem/3033

3033번: 가장 긴 문자열

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int HASH_SIZE = 100003;

int Mod(long long x)
{
    if (x >= 0)
        return x % HASH_SIZE;
    return ((-x / HASH_SIZE + 1) * HASH_SIZE + x) % HASH_SIZE;
}

int main()
{
    int L;
    string str;
    cin >> L >> str;

    int start = 0, end = L;
    while (start + 1 < end) {
        vector <int> hash[HASH_SIZE];
        int mid = (start + end) / 2, h = 0, po = 1;
        bool found = false;

        // 해시값(h) 만들기
        for (int i = 0; i <= L - mid; i++) {
            if (i == 0) {
                for (int j = 0; j < mid; j++) {
                    h = Mod(h + 1LL * str[mid - j - 1] * po);
                    if (j < mid - 1)
                        po = Mod(po * 2);
                }
            }
            else
                h = Mod(2 * (h - 1LL * str[i - 1] * po) + str[i + mid - 1]);

            if (!hash[h].empty()) {
                // 해시 충돌일 때 str의 [i, i+m-1]와 [p, p+mid-1]의 문자열이 같은지 비교
                for (int p : hash[h]) {
                    for (int j = 0; j < mid; j++) {
                        if (str[i + j] != str[p + j])
                            break;
                        if (j == mid - 1)
                            found = true;
                    }
                }
            }

            if (!found)
                hash[h].push_back(i);
        }

        if (found)
            start = mid; // 찾았으면 더 높은 길이 탐색
        else
            end = mid; // 없으면 더 낮은 길이 탐색
    }

    cout << start;
}

 

3. 맨버-마이어스 알고리즘

접미사 배열을 빠르게 구하기 위한 알고리즘이다.

 

1) 기본 원리

접미사 배열(Suffix Array)은 어떤 문자열의 모든 접미사를 사전 순으로 정렬해 둔 배열이다.

 

예를 들어 문자열 banana로 sa[i] 배열을 구해보자. 접미사는 a, na, ana, nana, anana, banana가 있고, 그것들을 사전 순으로 정렬하면 다음과 같다. 이때, sa[i] 배열에는 접미사 문자열을 저장할 순 없으니 해당 접미사의 첫 번째 인덱스를 저장한다.

 

i	sa[i]	S[sa[i]]
0	5	a
1	3	ana
2	1	anana
3	0	banana
4	4	na
5	2	nana

 

여기서 접미사 배열을 만들기 위한 여러 알고리즘이 있지만, 그중 맨버-마이어스 알고리즘을 활용할 것이다. 원리는 접미사를 첫 한 글자, 첫 두 글자, 첫 네 글자, 첫 여덟 글자... 첫 d*2 글자 씩 비교해가며 정렬하는 것이다.

 

첫 한 글자(d=0) 기준일 때, 그룹 3개로 나뉘며 그룹 1과 그룹 3에 추가 계산이 필요하다.

• 그룹 1: anana, ana, a
• 그룹 2: banana
• 그룹 3: nana, na

첫 두 글자(d=1) 기준일 때, 그룹 4개로 나뉘며 그룹 2와 그룹 4에 추가 계산이 필요하다.

• 그룹 1: a
• 그룹 2: anana, ana
• 그룹 3: banana
• 그룹 4: nana, na

마지막으로 첫 네 글자(d=2) 기준일 때, 드디어 모든 접미사가 각각의 그룹으로 나뉘었다. (그룹수 = 접미사수)

• 그룹 1: a
• 그룹 2: ana
• 그룹 3: anana
• 그룹 4: banana
• 그룹 5: na
• 그룹 6: nana

 

한 번 다른 그룹에 속한 접미사들은 다시 같은 그룹에 속할 수 없고 같은 그룹에 속하려면 첫 d*2 글자가 같아야 한다.

 

첫 한 글자(d=0) 기준일 때로 시작해 처음 그룹을 나눈 후 그다음 루프부터는 각 접미사가 이전 루프에서 몇 번째 그룹에 속했는지 안다면 1차적인 비교가 가능하다.

• 두 접미사가 이전 루프에서 그룹 번호가 다르다면, 그룹 번호가 클수록 사전 순으로 뒤에 있는 것이다.
• 두 접미사가 이전 루프에서 그룹 번호가 같다면, 그제야 d*2 글자부터 비교한다. 이때, d*2 글자부터 끝까지도 문자열의 접미사 중 하나가 되므로 다시 그룹 번호로 비교한다.

 

2) 문제

https://www.acmicpc.net/problem/9248

9248번: Suffix Array

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int sa[500000], lcp[500000];
int g[500000], tg[500000];

string s;
int n, t;

bool compare(int a, int b)
{
	if (g[a] == g[b])
		return g[a + t] < g[b + t];
	return g[a] < g[b];
}

void SuffixArray()
{
	t = 1, g[n] = -1;
	for (int i = 0; i < n; i++) {
		sa[i] = i;
		g[i] = s[i] - 'a'; // 첫 번째 루프는 제자리 문자로 비교
	}

	while (t <= n) {
		sort(sa, sa + n, compare);

		// 앞에서부터 각 접미사가 다른 그룹에 속할 때마다 그룹 번호를 증가시킨다.
		for (int i = 1; i < n; i++)
			tg[sa[i]] = tg[sa[i - 1]] + (compare(sa[i - 1], sa[i]) ? 1 : 0);

		t *= 2;
		for (int i = 0; i < n; i++)
			g[i] = tg[i];
	}
}

void LCP()
{
	int tmp[500000]{};
	for (int i = 0; i < n; i++)
		tmp[sa[i]] = i;

	int len = 0;
	for (int i = 0; i < n; i++) {
		if (tmp[i]) {
			int j = sa[tmp[i] - 1];
			while (s[j + len] == s[i + len])
				len++;

			lcp[tmp[i]] = len;

			if (len)
				len--;
		}
	}
}

int main()
{
	cin >> s;

	n = s.length();
	SuffixArray();
	LCP();

	for (int i = 0; i < n; i++)
		cout << sa[i] + 1 << " ";
	cout << "\nx ";
	for (int i = 1; i < n; i++)
		cout << lcp[i] << " ";
}

 

4. 아호 코라식 알고리즘(Aho-Corasick Algorithm)

• 일대다 패턴 매칭 알고리즘으로 문자열 하나 안에 여러 각각의 문자열이 존재하는지를 판별한다.
• KMP 알고리즘의 확장이다.

 

1) 기본 원리

그림을 보면 알겠지만, 일종의 트라이이다.

 

아호 코라식 알고리즘

 

• 문자열 S 내 문자 c를 하나씩 읽어가며 진행하는데, 시작 state는 제일 왼쪽 노드이다.
• 다음 state는 go 함수로 정의하며 이 함수를 통해 이동한다.
• output 노드(빨간 노드)에 도착했다면, 노드에 적혀있는 문자열이 문자열 S에 등장한다는 뜻이다.
• 만약 갈 곳이 없어지면, 단순히 시작 지점이 아니라 fail 함수를 통해 다른 어떤 곳으로 보낸다.

 

정리하자면 다음 state로 이동하는 메커니즘은 다음과 같다.

1. 현재 state x, 인풋 c에 대해 go(x, c)가 있으면 해당 노드로 이동한다.

2. 만약 없다면, fail(x)로 이동한 후 1로 돌아간다. 단, 이미 루트면 아무것도 하지 않는다.

 

여기서 fail 함수를 얼마나 효율적이게 구현하느냐가 포인트이다.

• fail 함수는 반드시 자신보다 깊이가 작은 노드를 가리킨다. (루프 노드 제외)
• fail(x)=y이면, y는 x의 접미사 중 가장 긴 접미사이다. (x 자신 제외)

 

2) 문제

https://www.acmicpc.net/problem/9250

9250번: 문자열 집합 판별

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

struct Trie {    
    Trie* go[26]; // 현재 노드에서 해당 문자를 받으면 가는 노드    
    Trie* fail; // 현재 노드에서 해당 문자의 go 목적지가 없을 때 가는 노드
    bool output; // 현재 노드에 도달하면 찾는 문자열 집합 있는지 판단

    Trie() 
    {
        fill(go, go + 26, nullptr);
        output = false;
    }

    ~Trie() 
    {
        for (int i = 0; i < 26; i++)
            if (go[i])
                delete go[i];
    }

    void insert(string key)
    {
        if (key == "\0") {
            output = true;
            return;
        }

        int next = key[0] - 'a';
        if (!go[next])
            go[next] = new Trie;

        // 맨 앞 문자는 제외하고 전달한다.
        go[next]->insert(key.substr(1, key.size() - 1));
    }
};

int main()
{
    int N, M;
    string str;
    Trie* root = new Trie;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> str;
        // 트라이에 S의 원소들을 모두 집어넣는다.
        root->insert(str);
    }

    // 트라이 노드를 방문하며 fail 함수를 만든다.
    queue<Trie*> q;
    root->fail = root;
    q.push(root);
    while (!q.empty()) {
        Trie* current = q.front();
        q.pop();

        // 26개의 input 각각에 대해 처리한다.
        for (int i = 0; i < 26; i++) {
            Trie* next = current->go[i];
            if (!next)
                continue;

            // 루트의 fail은 루트다.
            if (current == root)
                next->fail = root;
            else {
                Trie* dest = current->fail;

                // fail을 참조할 가장 가까운 조상을 찾아간다.
                while (dest != root && !dest->go[i])
                    dest = dest->fail;

                // fail(px) = go(fail(p), x)
                if (dest->go[i])
                    dest = dest->go[i];

                next->fail = dest;
            }

            // fail(x) = y일 때, output(y) ⊂ output(x)
            if (next->fail->output)
                next->output = true;

            // 큐에 다음 노드 push
            q.push(next);
        }
    }

    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> str;

        Trie* current = root;
        bool result = false;
        for (int j = 0; str[j]; j++) {
            int next = str[j] - 'a';

            // 현재 노드에서 갈 수 없으면 fail을 계속 따라감
            while (current != root && !current->go[next])
                current = current->fail;

            // go 함수가 존재하면 이동. 루트면 이게 false일 수도 있다
            if (current->go[next])
                current = current->go[next];

            // 현재 노드에 output이 있으면 찾은 것이다.
            if (current->output) {
                result = true;
                break;
            }
        }

        cout << (result ? "YES" : "NO") << endl;
    }
}

 

참고

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘