(Text Search) C++의 텍스트 검색 알고리즘- 설명, 예제 및 코드

텍스트 검색 알고리즘은 텍스트 처리 및 정보 검색의 기본 방법입니다. 이 알고리즘을 사용하면 더 큰 텍스트 내에서 하위 문자열(또는 패턴)의 위치를 ​​찾고 식별할 수 있습니다.

작동 방식

1. 더 큰 텍스트(또는 문서) 조각과 검색할 하위 문자열로 시작합니다.
2. 텍스트의 각 문자를 순차적으로 반복합니다.
3. 하위 문자열을 하위 문자열과 길이가 같은 텍스트 부분과 비교합니다. 일치하는 항목이 있으면 현재 위치를 기록합니다.
4. 다음 위치로 이동하여 비교를 계속하십시오.

예

"알고리즘이 어떻게 작동하는지 알아보기 위해 이 텍스트 내에서 하위 문자열을 검색해 봅시다."

그리고 검색할 하위 문자열: "substring"

1. 위치 0에서 시작합니다. Let' "하위 문자열"과 비교하십시오. 일치하지 않습니다.
2. 위치 1로 이동합니다. et's "하위 문자열"과 비교합니다. 일치하지 않습니다.
3. 위치 2로 이동합니다. t's "와 "하위 문자열"을 비교합니다. 일치하지 않습니다.
4. 위치 3으로 이동합니다. 's s "하위 문자열"과 비교합니다. 일치하지 않습니다.
5. 위치 4로 이동합니다. se "하위 문자열"과 비교합니다. 일치하지 않습니다.
6. 위치 5로 이동합니다. sea "하위 문자열"과 비교합니다. 일치하지 않습니다.
7. 위치 6으로 이동합니다. earc "하위 문자열"과 비교합니다. 일치하지 않습니다.
8. 위치 7로 이동합니다. arch "하위 문자열"과 비교합니다. 일치하지 않습니다.
9. 위치 8로 이동합니다. rch "와 "하위 문자열"을 비교합니다. 일치하지 않습니다.
10. 위치 9로 이동합니다. ch w "하위 문자열"과 비교합니다. 일치하지 않습니다.
11. 위치 10으로 이동합니다. h wi "하위 문자열"과 비교합니다. 일치하지 않습니다.
12. 위치 11로 이동합니다. " wit 와 "하위 문자열"을 비교합니다. 일치하지 않습니다.
13. 위치 12로 이동합니다. with "하위 문자열"과 비교합니다. 일치하지 않습니다.
14. 위치 13으로 이동합니다. ithi "하위 문자열"과 비교합니다. 일치하지 않습니다.
15. 위치 14로 이동합니다. thin "하위 문자열"과 비교합니다. 일치하지 않습니다.
16. 위치 15로 이동합니다. hinn "하위 문자열"과 비교합니다. 일치하지 않습니다.
17. 위치 16으로 이동합니다. in t "하위 문자열"과 비교합니다. 일치하지 않습니다.
18. 위치 17로 이동합니다. n th "하위 문자열"과 비교합니다. 일치하지 않습니다.
19. 위치 18로 이동합니다. " thi 와 "하위 문자열"을 비교합니다. 일치하지 않습니다.
20. 위치 19로 이동합니다. this "하위 문자열"과 비교합니다. 일치하지 않습니다.
21. 위치 20으로 이동합니다. his "와 "하위 문자열"을 비교합니다. 일치하지 않습니다.
22. 위치 21로 이동합니다. is t "하위 문자열"과 비교합니다. 일치하지 않습니다.
23. 위치 22로 이동합니다. s te  "하위 문자열"과 비교합니다. 일치하지 않습니다.
24. 위치 23으로 이동합니다. ubst  "하위 문자열"과 비교합니다. 일치하지 않습니다.
25. 위치 24로 이동합니다. bstr "하위 문자열"과 비교합니다. 일치하지 않습니다.
26. 위치 25로 이동합니다. stre "하위 문자열"과 비교합니다. 일치하지 않습니다.
27. 위치 26으로 이동합니다. trin  "하위 문자열"과 비교합니다. 일치하지 않습니다.
28. 위치 27로 이동합니다. ring  "하위 문자열"과 비교합니다. 일치 항목을 찾았습니다. 위치 27을 기록합니다.

하위 문자열 "substring"은 텍스트 내 위치 27에서 찾을 수 있습니다.

C++의 예제 코드

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

이 예에서 textSearch 함수는 텍스트 내에서 하위 문자열 "substring"의 위치를 ​​찾는 데 사용됩니다. 결과는 경기의 시작 위치를 포함하는 벡터입니다.