[종만북] 20장 문자열

종만북 20장 문자열

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

➖ 21-07-22

도입

• S의 부분 문자열(substring)
  = 문자열 S의 i번 글자부터 j번 글자까지로 구성된 문자열
  = S[i..j]

• S의 접두사(prefix)
  = 문자열 S의 0번 글자부터 a번 글자까지로 구성된 문자열
  = S[...a]

• S의 접미사(suffix)
  = 문자열 S의 b번 글자부터 끝까지로 구성된 문자열
  = S[b...]

문자열 검색

• 문자열 검색 문제 (짚더미(haystack)에서 바늘(needle)찾기)
  = 주어진 긴 문자열 H가 문자열 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제
  만약 N이 두번 이상 출현한다면 문자열 검색 알고리즘은 N이 출현하는 모든 위치 반환해야

• 가장 간단한 방법: N의 가능한 모든 시작 위치를 다 시도
  -> 전체 시간 복잡도 O( |H| * |N| )
  -> 구현이 단순하여 표준 라이브러리의 구현에 사용됨
  (C의 strstr(), C++ 문자열의 string::find(), ...)

//H의 부분 문자열로 N이 출현하는 시작 위치들을 모두 반환
vector<int> naiveSearch(const string& H, const string& N){
	vector<int> ret;
	//모든 시작 위치를 다 시도
	for(int begin = 0; begin < 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;
}

KMP 알고리즘

• 커누스-모리스-프랫(Knuth-Moris-Pratt) 알고리즘
  = KMP 알고리즘

• 현재 시작 위치에서 H와 N을 비교했을 때 몇 글자나 일치했는가를 이용하여
  현재 H내에서의 뮈치나 H에 포함된 문자들을 보지 않고도
  시작 위치 중 일부는 답이 될 수 없음을 보지 않고도 알 수 있다

• 일치한 글자의 수는 0 ~ |N|사이의 정수이기 때문에, 전처리 과정에서 이 정보들을 미리 계산해 저장해 둘 수 있다

다음 시작 위치 찾기

• 시작 위치 i에서 H와 N을 비교했을 때 matched 글자가 일치하고, 다음 글자가 불일치한 상황
  = H[ i .. i+matched-1 ]가 N[ ... matched-1 ]와 일치

• 시작 위치 i + k에서 답을 찾을 수 있기 위해서는N[ ... matched-1 ]의 길이 matched - k인 접두사와 접미사가 같아야 한다

• 답이 될 수 있는 바로 다음 위치를 찾기 위해서는 N의 각 접두사에 대해 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해 두면 된다
  -> 전처리 과정에서 부분 일치 테이블(partial match table) pi[] 계산
  -> pi[i]: N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이

실제 문자열 검색의 구현

• 시작 위치 i에서 H와 N을 비교했을 때 matched 글자가 일치하고, 다음 글자가 불일치한 상황
  -> 시작 위치 matched - pi[matched-1] 만큼 증가

• 시작 위치를 움직인 이후 첫 글자부터 다시 대응시켜 나갈 필요 X
  -> N의 첫 pi[matched-1] 글자는 대응되는 H의 글자와 일치한다는 사실을 이미 알고 있다
  -> matched를 pi[matched-1]로 변경하고 비교를 계속한다

• matched = 0인 경우는 예외 처리
  -> 모든 글자가 불일치한 경우 바로 다음 시작 위치에서 처음부터 다시 검색을 재개하는 방법 밖에 없다

//KMP 알고리즘을 이용하여 H의 부분 문자열로 N이 출현하는 시작 위치들을 모두 반환
vector<int> kmpSearch(const string& H, const string& N){
	int n = H.size();
	int m = N.size();
	
	vector<int> ret;
	//pi[i]: N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이
	vector<int> pi = getPartialMatch(N);
	
	//begin = matched = 0 부터 시작
	int begin = 0, matched = 0;
	while(begin <= n-m){
		//H의 해당 글자가 N의 해당 글자와 같은 경우
		if(matched < m && H[begin + matched] == N[matched]){
			++matched;
			//N의 모든 글자가 일치한 경우 답에 추가
			if(matched == m) ret.push_back(begin);
		}
		else{
			//matched = 0인 경우 다음 시작 위치에서 처음부터 다시 검색을 재개
			if(matched == 0) ++begin;
			else{
				begin += matched - pi[matched-1];
				matched = pi[matched-1];
			}
		}
	}
	return ret;
}

• kmpSearch()의 반복문의 전체 수행 횟수 O(|H|)
  -> 문자열 N의 길이와 상관 없이 문자열 H의 길이에만 비례

부분 일치 테이블 생성하기

• getPartialMatch() 함수 구현하기

• 가장 간단한 방법: N의 각 접두사에 대해 가능한 답을 하나씩 모두 시도
  -> 길이 p인 접두사 N[ ... p-1]이 주어졌을 때 길이 p-1인 접두사, 길이 p-2인 접두사, 길이 p-3인 접두사, ... 를 순회하며 N[ ... p-1]의 접미사가 되는지 확인
  -> 시간 복잡도 O( |N|^3 )

• 최적화할 수 있는 방법: 각 접두사에 대해 pi[]값을 따로 계산하는 것이 아니라 모든 접두사에 대해 한꺼번에 계산
  -> 두 글자 N[i]와 N[begin+i]가 일치할 때마다 pi[begin + i] 갱신
  -> 시간 복잡도 O( |N|^2 )

• pi[begin + i] = max(pi[begin + i], i + 1)
  -> 현재보다 왼쪽에 있는 시작 위치에서 이 위치의 값을 갱신했을지도 모르기 때문에 이미 있는 값과 i+1 중 큰 값을 선택한다

//N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi[]계산
//pi[i]: N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이
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; ++begin){
			if(N[i] != N[begin+i]) breaK;
			//i+1 글자가 서로 대응됨
			pi[begin + i] = max(pi[begin + i], i + 1);
		}
	}
	return pi;
}

• KMP 알고리즘 이용하여 부분 일치 테이블 생성하기
  -> 일치가 일어날 때마다 pi[]를 갱신하는 것을 제외하면 문자열 검색과 거의 똑같다
  -> 시간 복잡도 O( |N| )

vector<int> getPartialMatch(const string& N){
	int m = N.size();
	vector<int> pi (m,0);
	
	//KMP 알고리즘을 이용하여 문자열 검색
	//N에서 N을 찾는다
	//begin = 0이면 자기 자신을 찾아버리므로 begin = 1부터 시작
	int begin = 1;
	int matched = 0;
	//비교할 문자가 N의 끝에 도달할 때 까지 찾으면서 부분 일치를 모두 기록
	while(begin + matched < m){
		if(N[matched] == N[begin + matched]){
			++matched;
			//pi[]의 각 원소는 한 번만 변경되기 때문에 max()연산 필요X
			pi[begin + matched - 1] = matched;
		}
		else{
			if(matched == 0) ++begin;
			else{
				//begin을 옮길 때 이전에 계산한 pi[]값 사용
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

⚡접두사/접미사 (NAMING)

• 긴 문자열 S가 주어질 때 이 문자열의 접미사도 되고 접두사도 되는 문자열들의 길이를 전부 출력하는 문제

• ex. S = "ababbaba" 라고 하면 "a", "aba"는 이 문자열의 접미사도 되고 접두사도 된다
  -> 답: 1, 3, 8(=|S|)

• 간단한 방법: S의 모든 접두사에 대해 문자열 S의 접미사이기도 한지 확인
  -> |S|개의 접두사가 있고 각 접두사를 확인하는 데 접두사의 길이에 비례하는 시간이 걸린다
  -> 시간 복잡도 O(|S|^2)

• KMP 알고리즘에서 사용하는 부분 일치 테이블 pi[]를 만들면 접두사도 되고 접미사도 되는 문자열의 최대 길이를 구할 수 있다
  -> S = "ababbaba" 일 때 pi[7] = 3
  -> 이보다 짧은 답은 어떻게 구할 수 있을까?

• S의 길이 k인 접두사와 접미사는 서로 같다
  따라서 길이가 k이하인 S의 접미사는 S[...k-1]의 접미사이기도 하다
  -> ex. S = "ababbaba"에서 "aba"보다 짧은 답 "a"는 S의 접미사이기도 하지만, S[...2] = "aba"의 접미사 이기도 하다
  -> 따라서 k 다음으로 짧은 접미사를 찾으려면 p[k-1]을 확인하면 된다

//s의 접두사도 되고 접미사도 되는 모든 문자열의 길이를 반환
vector<int> getPrefixSuffix(const string& s){
	vector<int> ret;
	vector<int> pi = getPartialMatch(s);
	int k = s.size();
	while(k > 0){ 
		ret.push_back(k);
		k = pi[k-1];
	}
	return ret;
}

팰린드롬 만들기 (PALINDROMIZE)

• 팰린드롬(palindrome): 앞에서 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열

• 주어진 문자열 S 뒤에 적절한 문자열을 붙여서 S를 팰린드롬으로 만들려고 한다
  문자열 S를 뒤집은 문자열을 S뒤에 붙이면 항상 팰린드롬이 되지만, 결과 팰린드롬이 가능한 한 짧았으면 한다

• ex. S = "anon"일 때
  -> "nona"를 붙여서 "anonnona"로 만들 수 있다
  -> "ona"를 붙여서 "anonona"로 만들 수 있다
  -> "a"를 붙여서 "anona"로 만들 수 있다

• 문제를 푸는 방법: 우선 S를 뒤집은 문자열 S′을 만든 뒤, S의 접미사이면서 S′의 접두사인 문자열을 찾는다
  -> 이 문자열을 제외한 S′의 남은 부분을 S의 뒤에 붙이면 팰린드롬을 만들 수 있다

• 0부터 |S| - 1까지의 시작 위치들을 전부 시도하면서, S′이 S의 남은 부분들과 전부 일치하는 위치를 찾는다
  그런 위치가 여러개 있다면 항상 첫 번째 위치를 찾는다
  -> 겹치는 문자열의 길이가 길수록 만들어지는 팰린드롬의 길이가 짧아지기 때문

//KMP 알고리즘 변형
//a의 접미사이면서 b의 접두사인 문자열의 최대 길이를 구한다
int maxOverlap(const string& a, const string& b){
	int n = a.size();
	int m = b.size();
	vector<int> pi = getPartialMatch(b);
	
	//begin = matched = 0 에서 시작
	int begin = 0;
	int matched = 0;
	while(begin < n){
		if(matched < m && a[begin + matched] == b[matched]){
			++matched;
			//a의 마지막 글자와 b의 문자가 서로 일치했을 때
			//지금까지 일치한 부분의 길이 반환
			if(begin + matched == m)
				return matched;
		}
		else{
			if(matched == 0) ++begin;
            else{
            	begin += matched - pi[matched - 1];
            	matched = pi[matched-1];
            }
		}
	}
	return 0;
}

📌참고자료

• 접두사/접미사(NAMING) 풀이
  https://dontdiethere.tistory.com/102

• 전체 문자열은 접두사와 접미사가 같기 때문에 가장 먼저 문자열의 길이를 정답으로 넣어준다
• 그 다음의 위치 k를 pi[k-1]로 가르키면서 k가 0이 될 때까지 반복해주면 답을 구할 수 있다

➖ 21-07-23

KMP 알고리즘의 다른 구현

• KMP 알고리즘의 전통적인 구현
  -> 이 코드에서 마지막으로 본 문자열 H의 글자 번호인 i는 이전 코드의 begin+matched와 같다

vector<int> kmpSearch2(const string& H, const string& N){
	int n = H.size();
	int m = N.size();
    vector<int> ret;
    vector<int> pi = getPArtialMatch(N);
    //현재 대응된 글자 수
    int matched = 0;
    //문자열 H의 각 글자 순회
    for(int i = 0; i <n; ++i){
    	//matched번 글자와 H의 해당 글자가 불일치할 경우
    	//현재 대응된 글자 수를 pi[matched-1]로 줄인다
    	while(matched > 0 && H[i] != N[matched])
    		matched = pi[matched-1];
    	//글자가 대응될 경우
    	if(H[i] == N[matched]){
    		++matched;
    		if(matched == m) ret.push_back(i);
    		matched = pi[matched-1];
    	}
    }
}

📌참고자료

• KMP 알고리즘의 전통적인 구현
  https://www.youtube.com/watch?v=yWWbLrV4PZ8

➖ 21-07-27

접미사 배열

• 접미사 배열 (suffix array): S의 모든 접미사를 사전순으로 정렬해 둔 것
  -> 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현

접미사 배열을 이용한 문자열 검색

• 문자열 H가 문자열 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사
  -> H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다

• 접미사 배열의 길이 는 항상 |H|이므로 이진 탐색 내부 수행 횟수: O( lg|H| )번
  이진 탐색 내부에서 문자열 비교 시간: O( |N| )
  -> 이진 탐색 수행 시간 O( |N| lg|H| )

접미사 배열의 생성

• 접미사 배열을 계산하는 단순 알고리즘
  -> 별도의 비교자를 구현하여 C++ STL sort() 이용
  -> sort() :O(n) 시간이 걸리는 비교 O(nlgn)번 수행
  -> 전체 시간 복잡도: O(n^2 lgn)

//두 접미사의 시작 위치 i,j가 주어질 때 두 접미사 중 어느 쪽이 앞에 와야 할지 비교
struct SuffixComparator{
	const string& s;
	//구조체 생성자
	SuffixComparator(const string& s): s(s) {}
	
	bool operator () (int i, int j){
		//s.substr()대신에 strcmp()를 사용하여 임시 객체를 만드는 비용 절약
		//c_str(): c++ string을 c style char*로 변환
		//s.c_str() + i < s.c_str() + j 이면 true
		return strcmp(s.c_str() + i, s.c_str() + j) < 0;
	}
};

//s의 접미사 배열을 계산한다
vector<int> getSuffixArrayNaive(const string& s){
	//접미사의 시작 위치를 담은 배열
	vector<int> perm;
	for(int i = 0; i < s.size(); ++i)
		perm.push_back(i);
		
	//접미사를 비교하는 비교자를 이용하여 정렬
	sort(perm.begin(), perm.end(), SuffixComparator(s));
	return perm;
}

접미사 배열을 만드는 맨버-마이어스 알고리즘

• 맨버- 마이어스 알고리즘: 접미사들의 목록을 매번 그 기준을 바꿔서 여러 번 정렬
  -> 처음에는 접미사의 첫 한 글자만을 기준으로 정렬
  -> 다음에는 접미사의 첫 두 글자만을 기준으로 정렬
  -> 그 다음에는 접미사의 첫 네 글자만을 기준으로 정렬
  -> ...
  -> nlgn번의 정렬을 하고 나면 우리가 원하는 접미사 배열을 얻는다

• 정렬을 여러 번 하는 데도 더 빠르게 동작하는 이유:
  이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)에 할 수 있다

• group[i] = S[i..]가 속한 그룹의 번호

• 첫 t 글자를 기준으로 만든 group[]이 있을 때
  S[i..], S[j..] 중 첫 t 글자를 기준으로 어느 쪽이 더 앞에 오는 지 확인하는 방법:
  group[i]와 group[j]를 비교하면 알 수 있다

• S[i..], S[j..] 중 첫 2t 글자를 기준으로 어느 쪽이 더 앞에 오는 지 확인하는 방법:
  우선, 첫 t 글자를 기준으로 어느 쪽이 더 앞에 오는지 확인
  -> group[i]와 group[j] 비교
  만약 두 접미사가 같은 그룹에 속한다면, S[i+t..]와 S[j+t ..]의 첫 t 글자를 기준으로 어느 쪽이 더 앞에 오는지 확인
  -> group[i+t]와 group[j+t] 비교

• 첫 t 글자로 묶인 그룹 정보를 이용해 첫 2t 글자를 비교하는 비교자의 구현

//각 접미사들의 첫 t 글자를 기준으로 한 그룹 번호가 주어질 때
//주어진 두 접미사를 첫 2t 글자를 기준으로 비교한다
//group[]은 길이가 0인 접미사도 포함한다
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){
		//첫 t 글자가 다른 그룹에 속하는 경우
		if(group[a] != group[b]) return group[a] < group[b];
		//첫 t 글자가 같은 그룹에 속하는 경우
		return group[a+t] < group[b+t];
	}
};

• group[a+t]와 group[b+t]가 배열 밖의 범위인지 확인할 필요 X
  -> group[a+t]와 group[b+t]를 참조하는 경우 = group[a]와 group[b]가 같은 경우 = 두 접미사의 첫 t 글자가 같은 경우
  -> S[a..]와 S[b..]는 서로 다른 두 접미사이기 때문에 두 접미사의 길이는 모두 t 이상이 된다
  (a+t 와 b+t는 최대 n)

• ⚡접미사 배열을 계산하는 맨버와 마이어스 알고리즘

//s의 접미사 배열을 계산한다
vector<int> getSuffixArray(const string& s){
    int n = s.size();
    //group[i] = 접미사들을 첫 t 글자를 기준으로 정렬했을 때, 
    //S[i..]이 들어가는 그룹의 번호
    //t = 1일 때는 S[i..]의 첫 글자로 그룹 번호를 정해줘도 같은 효과가 있다
    int t = 1;
    vector<int> group(n+1);
    //S[n..]: 길이가 0인 접두사는 -1 번 그룹에 고정
    group[n] = -1;
    for(int i = 0; i<n; ++i)
    	group[i] = s[i];
    
    //결과적으로 접미사 배열이 될 반환값
    //접미사의 시작 위치 저장
    vector<int> perm(n);
    //모든 접미사의 시작 위치 저장
    for(int i = 0; i<n; ++i)
    	perm[i] = i;
    	
    while(t < n){
    	//첫 t 글자를 기준으로 계산된 group[]을 이용하여
    	//첫 2t 글자를 기준으로 perm[]을 다시 정렬한다
    	Comparator compareUsing2T(group, t);
    	sort(perm.begin(), perm.end(), compareUsing2T);
    	
    	t *= 2;
    	if(t >= n) break;
    	
    	//첫 2t 글자를 기준으로 group[] 새로 계산
    	vector<int> newGroup(n+1);
    	//S[n..]: 길이가 0인 접두사는 -1 번 그룹에 고정
    	newGroup[n] = -1;
    	for(int i = 1; i<n; ++i){
    		if(compareUsing2T(perm[i-1], perm[i])){
    			newGroup[perm[i]] = newGroup[perm[i - 1]] + 1; 
    		}
    		else{
    			newGroup[perm[i]] = newGroup[perm[i - 1]]; 
    		}
    	}
    	//group[] 갱신
    	group = newGroup;
    }
    return perm;
}

원형 문자열

• 길이 n(n<=40000)인 문자열을 끝과 끝이 연결된 원형으로 써보자
  이 문자열을 항상 시계 방향으로 읽는 데, 시작 위치가 어디인지는 정해져 있지 않으므로 n가지 방법으로 읽을 수 있다
  이 중 사전순으로 가장 앞에 오는 문자열은?

• 주어진 문자열 S를 두 번 반복한 문자열 S2 를 만든다
  이때 S를 읽을 수 있는 방법은 모두 S2의 부분 문자열이 된다
  -> S2의 접미사 배열을 만든 뒤, 가장 앞에 오는 길이가 n 이상인 접미사를 찾으면 된다

//사전순으로 가장 앞에 오는 s의 회전 결과를 구한다
string minShift(const string& s){
	string s2 = s + s;
	vector<int> a = getSuffixArray(s2);
	for(int i = 0; i<a.size(); ++i)
		//접미사가 시작하는 위치 a[i]가 s.size()보다 커지면
		//접미사의 길이가 s.size()보다 짧아진다
		if(a[i] <= s.size())
			return s2.subarray(a[i], s.size());
    //여기까지 올 일은 없어야 한다
    return "__oops__"
}

📌참고자료

• string의 c_str 함수
  https://modoocode.com/297

• C++의 string을 C style의 char*로 변환
  -> c_str() ~ c_str() + size() 까지 C++의 string이 저장되어 있고, 맨 마지막 위치에 NULL 문자가 오게 된디
• c_str() 이 리턴하는 배열을 수정하는 것은 정의되지 않는 작업 (undefined behavior)이다

• string의 strcmp 함수
  https://blockdmask.tistory.com/391

• 매개변수로 들어온 두 개의 문자열을 비교하여 문자열이 완전히 같다면 0을 반환하고,
  다르면 음수 혹은 양수를 반환하는 함수
  -> str1 < str2 인 경우에는 음수 반환
  -> str1 > str2 인 경우에는 양수 반환
  -> str1 == str2 인 경우에는 0을 반환
• 앞에서 부터 각각 문자를 비교할때, 아스키 코드값으로 비교를 하게 됩니다.

➖ 21-07-28

서로 다른 부분 문자열의 수

• 길이 n(n<= 4000)인 문자열은 최대 n(n+1)/2 개의 부분 문자열을 가질 수 있지만, 이들이 모두 서로 다른 것은 아니다
  문자열이 주어질 때 이들의 서로 다른 부분 문자열의 수를 세는 문제

• 가장 간단한 방법:
  각 부분 문자열을 직접 만들어 보면서 이들을 집합 자료 구조에 넣는 것
  -> O(n^2)개의 부분 문자열
  C++ set< > 자료구조 넣기 위한 비교 횟수: O(lgn)번
  문자열 비교 시간: O(n)
  -> 전체 시간 복잡도 O(n^3 lgn)

접미사 배열을 이용해 푸는 방법

• S의 모든 부분 문자열은 접미사의 접두사로 표현할 수 있다
  -> 길이 m인 접미사는 m개의 접두사를 가진다

• 한 부분 문자열이 두 번 이상 출연할 경우 이를 접두사로 갖는 접미사들을 접미사 배열 상에서 항상 인접하다
  -> 따라서 한 부분 문자열이 이미 출현했는지를 알기 위해서는 바로 위 접미사만을 보면 된다

• 각 접미사에 대해 배열에서 자기 앞에 오는 배열과 최장 공통 접두사의 길이를 구하면, 이만큼은 중복되는 부분 문자열임을 이용할 수 있다

//s[i..]와 s[j..]의 공통 접두사의 최대 길이 계산
int commonPrefix(const string& s, int i, int j){
	int k = 0;
	while(i < s.size() && j < s.size() && s[i] == s[j]){
		++i; ++j; ++k;
	}
	return k;
}

//s의 서로 다른 부분 문자열의 수를 센다
int countSubstrings(const string& s){
	//문자열 s의 모든 접미사를 사전순으로 정렬해둔 벡터
	//접미사가 시작하는 위치 저장
	vector<int> a = getSuffixArray(s);
	
	int ret = 0;
	for(int i = 0; i < a.size(); ++i){
		int cp = 0;
		if(i > 0) cp = commonPrefix(s, a[i-1],a[i]);
		
		//a[i]의 (a.size() - a[i])개의 접두사들 중 cp개는 중복이다
		ret += s.size() - a[i] -  cp;
	}
	return ret;
}