[종만북] 문자열 검색 / 문자열

[종만북] 문자열 검색 / 문자열

[종만북] 문자열 검색 / 문자열

 

문자열

현대의 컴퓨터는 많은 양의 문자열 자료를 다룹니다. 문서 파일, 인터넷의 웹페이지. 이메일 그리고 문자 메시지들이 모두 다 문자열입니다. 때문에 문자열을 다루는 문제와 자료구조는 전산학의 중요한 연구 주제이며, 정보 검색 (Information retrieval) 이나 생물 정보학 (bioinformatics) 분야에서 특히 이용하게 사용됩니다.

문자열을 다루는 알고리즘 또한 매우 범위가 깊고 넓지만, 시간이 제한된 프로그래밍 대회 특성상 구현이 비교적 간단한 알고리즘이 주로 사용 됩니다.
- KPM 알고리즘 : 문자열 검색
- 접미사 배열 (suffix array) : 문자열 처리

 

용어에 관하여

문자열의 부분 문자열(substring), 접두사(prefix), 접미사(suffix) 에 대한 내용을 많이 다룹니다.
표현을 간결하게 하기 위하여 표기들을 정의합니다.

• 문자열의 길이: |S|
  • S = "avada" 일 때, |S| = 5
• S 의 i (0 <= i < |S| ) 번 글자: S[i]
  • S = "kedavra" 일 때, s[4] = v
• 문자열 S 의 i 번 글자부터 j 번 글자까지 구성된 S 의 부분 문자열 (substring): S[i...j]
  • S = "avada" 일 때, S[1...4] = "vada" / S[0...2] = "ava"
• 문자열 S 의 0 번 글자부터 a번 글자까지 구성된 S 의 접두사 (prefix): S[...a]
  • S = "kedavra" 일 때, S[...3] = "keda"
• 문자열 S 의 b 번 글자부터 끝번 글자까지 구성된 S 의 접미사 (suffix): S[b...]
  • S = "avada" 일 때, S[2...] = "ada"
  • b = |S| , S[b...] 는 길이가 0인 접미사

 

문자열 검색

주어진 긴 'haystack' 문자열 H 가 'needle' 문자열 N 을 부분 문자열로 포함하지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제

H = "hogwarts"
N = "gwart"
H[2...6] = N 이므로, N 의 시작위치는 2 가 된다.

H = "avava"
N = "ava"
H[0...2] = H[2...4] = N 이므로, N 의 시작 위치는 0 과 2 가 된다.
모든 시작위치를 반환하여야 한다.

 

// H 의 부분 문자열로 N 이 출현하는 시작 위치들을 모두 반환

vector<int> naiveSearch(const string& H, const string& N){
    vector<int> ret;
    
    // 가능한 시작 위치를 전부 시도
    for(int begin = 0; begin + N.size() <= H.size(); ++begin){
        bool matched = true;
        for(int i = 0; i < N.size(); i++)
            if(H[begin + i] != N[i]{
                match = false;
                break;
            }
        if(matched) ret.push_back(begin);
    }
	return ret;
}

• 문제를 푸는 가장 간단한 방법은 N 의 가능한 모든 시작 위치를 다 시도해 보는 것
  • 특정 입력 형태에 대해서 굉장히 비효율적으로 동작 : H 와 N 이 같은 문자로만 구성된 긴 문자열 일 경우
    • 모든 시작 위치가 답: |H| - |N| + 1 개의 모든 시작 위치에서 비교 수행
    • 시작 위치의 수: O(|H|) 
    • 한 시작점에서의 수행 시간: O(|N|)
    • 전체 시작 복잡도: O(|H| x O(|N|)) 
  • 입력이 큰 경우이 꽤 비효율적이지만 흔치 않은 경우이며, 구현이 단순하다는 장점이 있기 때문에 표준 라이브러리에 사용됨
    • C 의 strstr()
    • C++ 의 string::find()
    • JAVA 의 indexOf()
    • 등