알고스팟(algospot) 20장 문자열

20.1 도입

프로그래밍 대회에서는  비교적 간단한 알고리즘이 주로 사용됩니다...?

• 문자열 검색 kmp알고리즘
• 문자열 처리의 자료 구조 접미사 배열

등등 을 사용

 

 

20.2 문자열 검색

1. 단순 문자열 검색 알고리즘 : 하나씩 하나씩 비교

vector<int> naiveSearch(const string& H,   const string& N)   { 
	vector<int> ret; 
	for(int begin = 0;  begi n + N.size( )  <= H.size( ); ++begin)  { 
    		bool matched  = true; 
			for( int i  = 0;  i  < N. size() ;  ++i ) 
        	if(H [begin + i]  != N[i]) { 
				matched  = false; break; 
			} 
		if(matched) 
			ret.push_back(begin); 
		} 
	return ret; 
}

 단순하지만 비효율적;;;

 

 

2. KMP 알고리즘 : 접두사와 접미사가 같은 --> 부분 일치 테이블을 이용하여 문자열 검색 시 뛰어넘어버리는 알고리즘!

 

부분 일치 테이블? 

처럼 부분이 겹치는 것

 

 

구하는 방법 1. 단순 문자열 탐색

vector<int> getPartialMatchNaive(const string& N)  { 
	int m = N. size{) ; 
	vector<int> pi(m,  0) ; 

	for{int begin = 1;  begin < m;   ++begin)  { 
    	for( int i  = 0;  i  + begin < m;   ++i)  { 
			if(N [begin + i]  != N [i] )  
            	break; 
			pi[begin + i] = max(pi[begin + iL  i  + 1) ; 
		} 
    } 
	return pi; 
}

 

2. KMP를 이용해 일치 테이블 생성

 

vector<int~ getPartiatch(const string& N)  { 
	int m = N. size() ; 
	vector<int> pi(m,  0) ; 
	// KMP로 자기 자신을 찾는다. 

	int begin = 1, matched = 8; 

	while(begin + matched  < m)   { 
		if(N[begin + matched] = N[matched] )  { 
        	++matched; 
			pi[begin+matched-1]  = matched; 
		} 
		else { 
			if(matched = 0) ++begin; 
			else { 
				begin +=  matched  -  pi[matched-1); 
                		matched  = pi[matched-1]; 
			} 
		} 
	} 
	return pi; 
}

 

 

 

이런 식으로 구할 수 있음!

 

이걸 사용하여 탐색 후 

 

vector<int> kmpSearch(const  string& H,   canst string& N)   { 
	int n = H. size() ,  m = N. size() ; 
	vector<int> ret ; 
 
	vector<int> pi =  getPartialMatch(N);// 접미사와 접두사가 같은 문자열의 부분일치 테이블

	int begin = 0,  matched  = 0; while(begin <=  n -  m)   { 

	if(matched < m &&  H [begin + matched] = N [matched] )  { 
		++matched; 

		if(matched = m)  
        	ret.push_back(begin) ; 
		} 
        else { 

			if(matched = 0) 
				++begin; 
			else { 
				beg in +=  matched  -  pi [matched-1] ; 
				mat ched  = pi[matched-1]; 
			} 
		} 
	} 
	return  ret;  
}

 

출처 :

(C++) 문자열 검색 알고리즘 : KMP 알고리즘

 

20.5  접미사 배열

접미사 배열? -->한 문자열의 모든 접미사들을 사전 순으로 배열에 저장해 놓은 것

 

접미사 배열을 통해     찾으려는 단어 =  접미사의 접두사의 일치를 통해 보다 빠르게 검색 가능

 

접미사 배열을 만드는 방법?

 

단순 sort()를 사용하여 만드는 방법 --> 시간 복잡도가...

그래서 대부분  맨버 마이어스의 알고리즘을 사용!

 

 

맨버 마이어스

먼저 접미사의 첫 한 글자를 기준으로 정렬하고, 그다음으로는 두 글자, 네 글자, 여덟 글자... 순으로 정렬한다.

--> 정렬을 여러 번 하면 더 오래 걸리지 않나??

--> no 이전에 정렬했던 내용을 토대로 다시 정렬하기에 생각보다 빠르다!

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
struct Comparator {
    const vector<int>& group;
    int t;
    Comparator(const vector<int>& _group, int _t) :group(_group), t(_t) {
        group = _group
        t = _t;
    }
 
    bool operator()(int a, int b) {

        if (group[a] != group[b])return group[a] < group[b];
        return group[a + t] < group[b + t];
    }
};