close

C++의 문자열 검색 (String Search) 알고리즘- 설명, 예제 및 코드

문자열 검색 알고리즘은 더 큰 텍스트(문자열) 내에서 특정 패턴(하위 문자열)의 발생을 찾는 데 사용됩니다. 이 알고리즘은 텍스트 처리, 검색 및 조작 작업에서 중요한 역할을 합니다.

작동 방식

  1. 검색할 텍스트(문자열) 및 패턴(하위 문자열)으로 시작합니다.
  2. 한 번에 한 문자씩 텍스트를 반복합니다.
  3. 텍스트의 각 문자를 패턴의 첫 번째 문자와 비교합니다.
  4. 일치하는 경우 후속 문자도 패턴과 일치하는지 확인하십시오.
  5. 패턴이 완전히 일치하면 일치의 시작 위치를 기록합니다.
  6. 텍스트에서 패턴을 계속 검색합니다.

예

"ababcababcabcabc" 텍스트와 "abc" 패턴을 고려하십시오.

  1. 위치 0에서 시작합니다. "a"를 패턴의 첫 번째 문자 "a"와 비교합니다.
  2. 일치 항목이 발견되면 "b"와 "b", "c"와 "a"의 다음 문자로 이동합니다.
  3. "b"는 "a", "a"는 "b", "b"는 "c"와 계속 일치시킵니다.
  4. 위치 2에서 경기가 실패했습니다.
  5. 위치 3에서 다시 시작합니다. "a"를 패턴의 첫 번째 문자 "a"와 비교합니다.
  6. 성공적인 일치: "a"와 "a", "b"와 "b", "c"와 "c".
  7. 기록 위치 3.

패턴 "abc"는 위치 0, 6 및 9에서 찾을 수 있습니다.

C++의 예제 코드 

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

이 예에서 stringSearch 함수는 텍스트 "ababcababcabcabc" 내에서 패턴 "abc" 발생을 찾는 데 사용됩니다. 결과는 경기의 시작 위치를 포함하는 벡터입니다.