[작성중] 문자열 검색

---

KMP

하나의 패턴 문자열을 다른 문자열에서 효율적으로 검색하는데 사용됩니다.
주어진 패턴 문자열에서 일치하지 않는 문자를 기반으로 불필요한 비교를 최소화합니다.
KMP 알고리즘은 접두사와 접미사의 개념을 활용하여, 불일치가 발생한 위치를 이용해 다음 검색 위치를 결정합니다.
시간 복잡도는 O(N+M), 여기서 N은 텍스트 문자열의 길이, M은 패턴 문자열의 길이입니다.

 

검사하던 패턴에서 이미 검사한 부분은 건너뛴다는 내용같긴 한데 다른 블로그의 설명들이 많이 부실하다.

해당 내용에 대한 이해를 기반으로 쓴건지 복사해서 쓰는건지..

 

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260&categoryNo=299&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=&from=menu&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=4

---

아호코라식

Aho-Corasick 알고리즘은 여러 개의 패턴 문자열을 동시에 검색하는데 사용됩니다.
주어진 텍스트에서 여러 개의 패턴 문자열 중 일치하는 패턴을 찾아냅니다.
Aho-Corasick 알고리즘은 트라이(Trie) 자료구조와 유한 오토마타(Finite Automaton)를 결합한 형태로 동작합니다.
패턴 문자열들을 사전 형태로 구성하여 검색 시간을 최소화합니다.
시간 복잡도는 O(N+Z+P), 여기서 N은 텍스트 문자열의 길이, Z는 모든 패턴 문자열의 길이의 총합, P은 찾아낸 패턴의 수입니다.

 

"abcde", "aef" 라는 패턴이 있다면 trie_node* root의 children 으로 잘라서 구성해준다.

 

trie_node : root

"abcde"

  └ trie_node : a  => root의 children

    └ trie_node : b  => a의 children

      └ trie_node : c => b의 children

        └ trie_node : d => c의 children

          └ trie_node : e => d의 children

"aef"

  └ trie_node : a  => root의 children

    └ trie_node : e  => a의 children

      └ trie_node : f => e의 children

 

검색할 문자열을 한 글자씩 root부터 타고 들어가면서 문자를 비교하고 끝까지 간 node가 글자의 끝이라면 발견

 

struct trie_node
{
    std::unordered_map<char, trie_node*> children;
    trie_node* failure_link;
    bool is_end_of_word;
    std::size_t index;

    trie_node()
        : failure_link(nullptr)
        , is_end_of_word(false)
        , index(-1)
    {
    }
};

// 트라이에 문자열을 삽입하는 함수
void insert_string(trie_node* _root, const std::string& _str, std::size_t _index)
{
    trie_node* current = _root;

    for (char c : _str)
    {
        if (current->children.find(c) == current->children.end())
        {
            current->children.insert({ c, new trie_node });
        }

        current = current->children[c];
    }

    current->is_end_of_word = true;
    current->index = _index;
}

// 트라이의 실패 링크를 구성하는 함수
void construct_failure_links(trie_node* _root)
{
    std::queue<trie_node*> q;

    for (auto& pair : _root->children)
    {
        pair.second->failure_link = _root;
        q.push(pair.second);
    }

    while (!q.empty())
    {
        trie_node* current = q.front();
        q.pop();

        for (auto [c, child] : current->children)
        {
            trie_node* failure = current->failure_link;

            while (failure != nullptr && failure->children.find(c) == failure->children.end())
            {
                failure = failure->failure_link;
            }

            if (failure == nullptr)
            {
                child->failure_link = _root;
            }
            else
            {
                child->failure_link = failure->children[c];
            }

            q.push(child);
        }
    }
}

// Aho-Corasick 알고리즘을 사용하여 문자열 매칭을 수행하는 함수
std::size_t search_patterns(trie_node* _root, const std::string& _text)
{
    trie_node* current = _root;
    std::size_t length = _text.length();

    for (std::size_t i = 0; i < length; ++i)
    {
        char c = _text[i];

        while (current != nullptr && current->children.find(c) == current->children.end())
        {
            current = current->failure_link;
        }

        if (current == nullptr)
        {
            current = _root;
        }
        else
        {
            current = current->children[c];
            if (current->is_end_of_word)
            {
                return current->index;
            }
        }
    }

    return -1;
}

int main()
{
    trie_node* root = new trie_node();
    std::vector<std::string> filter = { "!", u8"아녕", "aef", u8"んこにちは", "!?" };
    std::string text = u8"안녕하세요! Hello こんにちは 안녕.How are you? abcdef";

    for (std::size_t i = 0; i < filter.size(); ++i)
    {
        insert_string(root, filter[i], i);
    }

    construct_failure_links(root);

    std::size_t idx = search_patterns(root, text);
    if (idx != -1)
    {
        std::cout << "match:" << filter[idx] << std::endl;
    }

    return 0;
}

---