[c++] 스트링 검색 알고리즘

15 Dec 2023

C++ 프로그래밍에서 문자열을 검색하는 것은 매우 일반적입니다. 이를 위해 여러 가지 알고리즘이 사용됩니다. 여기서는 C++에서 스트링을 검색하는 두 가지 기본 알고리즘에 대해 살펴보겠습니다.

1. `find()` 함수

std::string 클래스는 find() 함수를 제공하여 특정 문자열 또는 문자가 처음으로 나타난 위치를 찾을 수 있습니다. find() 함수의 사용법은 다음과 같습니다:

std::string str = "Hello, world!";
std::size_t found = str.find("world");
if (found != std::string::npos) {
    // 문자열이 발견된 경우
    std::cout << "첫 번째로 발견된 위치: " << found << std::endl;
} else {
    // 문자열이 발견되지 않은 경우
    std::cout << "찾는 문자열이 없음" << std::endl;
}

2. KMP 알고리즘

KMP(Knuth-Morris-Pratt) 알고리즘은 특정 패턴을 검색하는 데 사용되는 효율적인 알고리즘입니다. C++ 에서 KMP 알고리즘을 구현하려면 보통 다음과 유사한 함수를 작성합니다:

void computeLPSArray(std::string pattern, int m, int lps[]) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

그런 다음 computeLPSArray() 함수를 사용하여 실제로 문자열을 검색할 수 있습니다.

이렇게 C++에서 스트링을 검색하는 방법에는 다양한 알고리즘이 있지만, find() 함수와 KMP 알고리즘은 가장 널리 사용되는 것 중에 하나입니다.

더 많은 정보를 원한다면, 다음 문서를 참고하세요. std::string::find - cppreference.com

이상으로 C++에서의 스트링 검색 알고리즘에 대한 간략한 소개를 마치겠습니다.

1. find() 함수

2. KMP 알고리즘

1. `find()` 함수