자료구조

본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

문자열 검색 I

 문자열 검색 혹은 패턴 매칭 알고리즘은 어떤 문자열 S에서 특정한 부분 문자열 P를 찾는 알고리즘을 말합니다.

예를 들어서 S를 "ABACABA", P를 "ABA"라고 해봅시다. 그러면 문자열 S에서 부분 문자열 P가 총 2번 등장합니다. 두 번 등장하는 위치는 아래의 표를 참고하세요.

A B A C A B A
A B A   A B A

 

Brute Force

 먼저 가장 직관적이고 단순한 방법으로 문자열을 검색하는 방법을 알아봅시다. 탐색하려고 하는 부분 문자열 P의 길이를 LP라고 해봅시다. 그렇다면 S의 부분 문자열 Si번째 문자부터 (i+LP-1)번째 문자까지의 부분 문자열이 P와 모든 문자가 일치한다면, S안에서 P를 찾았다고 할 수 있습니다.

 요약 하자면 검사하고 싶은 시작위치 i에 대해 다음의 과정을 수행하면 됩니다.

  - 검사를 시작할 지점 i를 하나 선택한다. 단, 0 <= i < LS

  - S[i]부터 S[i+LP-1] 모든 문자열을 비교한다.

  - 위의 과정에서 S의 부분 문자열과 P에 속한 문자가 모두 일치한다면 검색이 성공한 것이다.

 

이를 코드로 표현하면 아래와 같습니다.

#include<string>
#include<iostream>
using namespace std;

bool isMatched(const char *s, const char *p, int from)
{//s의 from번째부터 패턴 p가 발견되는가?
    int n = strlen(p);
    for(int i=0; i<n; i++)
    {
        if( *(s+from+i) != *(p+i) || *(s+from+i) == NULL)
            return false;
    }
    return true;
}

bool isMatchedCpp(const string &s, const string &p, int from)
{//s의 from번째부터 패턴 p가 발견되는가?
    int n = p.length();
    for(int i=0; i<n; i++)
    {
        
        if( s[i+from] != p[i] || (i+from) >= s.length() )
            return false;
    }
    return true;
}

//사용법
int main(){
    string s, p;
    cin >> s >> p;
    int cnt = 0;
    for(int i=0; i<s.length(); i++)
    {   //s의 i번째 위치부터 패턴 p가 발견되는가?
        if(isMatched(s, p, i) == true)
        {//패턴 존재 확인됨
            cnt ++;
        }
    }
    cout << "총 " << cnt << "번 등장"<<endl;
    return 0;
    
}

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
코딩몬스터
현재 버전
선택 버전
graphittie 자세히 보기