[Algorithms] String Matching Algorithm | 문자열 매칭 알고리즘

String Matching Algorithm

문자열 매칭 알고리즘

- 전체 문자열 string[n]에서 부분 문자열 pattern[m]이 존재하는지,
  존재한다면 pattern이 string에서 시작되는 인덱스 값을 리턴하는 알고리즘이다.
- 단순한 Brute-Force 방식의 String Matching 방법은 \O(n * m)에 비례하는 시간이 소요되며,
  Advanced-String Matching Algorithm은 대체로 \Theta(n + m)에 비례하는 시간이 소요된다.

---

Brute-Force String Matching Algorithm

* GitHub (URL)

vector<int> find_bf(const string &str, const string &pat)
{
    const int strSize = str.size();
    const int patSize = pat.size();

    if (strSize < patSize)
        throw "Main String must be greater than substring";

    vector<int> result(strSize - patSize + 1, -1);

    for (int i = 0; i < strSize - patSize + 1; i++)
    {
        int j=0;
        while (j < patSize)
        {
            if(str[i+j] == pat[j])
                j++;
            else
                break;
        }
        if(j == patSize)
            result.push_back(i);
    }

    return result;
}

---

Advanced String Matching Algorithm

* String Matching with Finite Automata (오토마타를 이용한 문자열 매칭) (URL)

* Rabin-Karp Algorithm (라빈-카프 알고리즘) (URL)

* KMP Algorithm (KMP 알고리즘) (URL)

* Boyer-Moore Algorithm (보이어-무어 알고리즘) (URL)

---

Reference: Introduction to Algorithms 3E
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: Fundamentals of Data Structure in C++
(Horowitz, Sahni, Mehta 저, Silicon Press, 2006)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)