B - Editor

B 는 이번 대회 문제들 중 A 와 함께 가장 많은 팀이 푼 문제로, 굉장히 다양한 종류의 해법이 있으며 이들 모두가 문제를 풀 수 있다는 점에서 매력적인 문제였습니다. 이들 방법들은 모두 시간 복잡도도 달랐는데, 대부분의 방법으로 큰 무리 없이 해결할 수 있었습니다.

이 문제를 간략하게 바꾸면 다음과 같습니다.

"소문자 알파벳 5,000개 이하로 구성된 문자열 S 가 주어질 때, S 의 부분 문자열은 S 의 연속된 일부를 잘라낸 것이다. 이 때 두 번 이상 등장하는 부분 문자열 중에서 가장 긴 것의 길이는?"

앞으로 편의를 위해서 다음과 같은 표기를 사용하겠습니다.

• S[i] = S 의 i번째 글자
• S[i:] = S 의 i번째 글자에서부터 시작하는 S 의 suffix
• S[i:j] = S 의 i번째 글자에서 시작하고 j번째 글자에서 끝나는 S 의 부분 문자열
• prefix: S 의 앞을 0글자부터 n글자까지 잘라낸 것
• suffix: S 의 뒤를 0글자부터 n글자까지 잘라낸 것

1. 가장 직관적이지만 너무 느린 O(n^3lgn)

가장 직관적인 방법은 S의 모든 부분 문자열을 생성해서 이들을 정렬하고, 중복이 있는지를 확인하는 것입니다. 아니면, map 와 같은 연관 컨테이너를 써서 각 부분 문자열의 개수를 셀 수 있겠지요. 이렇게요:

void solve1(const string& S)
{
      map<string,int> freq;
      for(size_t begin = 0; begin < S.size(); ++begin)
              for(size_t end = begin+1; end <= S.size(); ++end)
                      freq[S.substr(begin, end-begin)]++;
      int res = 0;
      for(map<string,int>::iterator it = freq.begin(); it != freq.end(); ++it)
              if(it->second > 1)
                      res = max<int>(res, it->first.size());
      cout << res << endl;
}

간단하죠? 하지만 이 방법은 O(n^2) 개의 부분 문자열을 모두 생성합니다. map 에 삽입하는 데 O(lg n) 번의 비교만 해도 된다고 하더라도, 각 문자열의 비교가 최대 O(n) 이기 때문에 전체의 시간 복잡도는 O(n^3lgn) 이 될 수밖에 없습니다. n = 5000 일때 n^3lgn = 1,535,964,047,443 정도 되는데.. 이래서야 시간 복잡도 안에 안 들어가겠지요.

2. 조금 더 나은 O(n^3)

모든 부분문자열을 생성하지 않으면 그보다 조금 나은 방법을 만들 수 있습니다. 이 아이디어는 모든 a, b 위치에 대해 S[a:] 과 S[b:] 의 가장 긴 prefix 의 길이를 매번 구하는 것입니다.
다음과 같은 함수로 이런 일을 할 수 있습니다.

// S[a:] 와 S[b:] 의 최대 공통 prefix 의 길이를 구한다
// 예: S[a:] = "abcdef" S[b:] = "abcefg" 라면 답은 3
int getPrefixLength(const string& s, int a, int b)
{
  int len = 0;
  while(a+len < s.size() && b+len < s.size() && s[a+len] == s[b+len]) ++len;
  return len;
}

getPrefixLength 를 모든 a 와 b 에 대해 호출하면 이 중 최대값이 답이 된다는 것은 비교적 자명합니다. 그런데 각 getPrefixLength() 함수 호출은 최대 O(n) 의 시간이 들고, 모든 a 와 b 의 조합은 O(n^2) 개가 있기 때문에 이 알고리즘은 O(n^3) 이 됩니다. 여전히 희망이 없어 보입니다. 그러나, 만약에 S[1] 이 "abcd.." 로 시작하고, S[372] 에서 시작하는 부분문자열이 "efgce.." 라고 하면, getPrefixLength() 는 한 번 조건문 판단하고 종료해 버리기 때문에 실제 실행에 드는 시간은 훨씬 적습니다.

5천개의 같은 문자가 들어올 경우 이 프로그램은 시간 안에 동작할 가능성이 별로 없습니다만, 실제 대회에서는 이 알고리즘으로 Yes 를 받은 팀이 있다고 합니다. (아주대학교 the pulza 팀)

3. 동적 계획법을 사용해서 O(n^2)

getPrefixLength() 함수는 a 와 b 가 정해져 있으면 언제나 같은 값을 반환합니다. 따라서, 이를 재귀함수로 다음과 같이 구현할 수 있습니다.

int getPrefixLength(const string& s, int a, int b)
{
  if(a == s.size() || b == s.size() || s[a] != s[b]) return 0;
  return getPrefixLength(s, a+1, b+1) + 1;
}

이 함수는 여전히 S[a:] 와 S[b:] 의 최대 공통 prefix 길이를 반환합니다. 다른 점은 재귀적으로 구현되어 있다는 것인데요.

• S[a:] 나 S[b:] 가 텅 빈 문자열이거나 (a == S.size() or b == S.size()), S[a] != S[b] 면 답은 0 입니다.
• 아니라면, S[a+1:] 과 S[b+1:] 의 최대 공통 prefix 앞에 S[a] 를 붙여서 최대 공통 prefix 를 만들 수 있습니다. 이렇게 문제를 재귀적으로 표 현하는 것은 동적 계획법(Dynamic Programming) 알고리즘의 기반이 됩니다. 동적 계획법 알고리즘은 이렇게 재귀적으로 표현된 문제의 부분해를 각각 저장해 속도를 올리는 알고리즘 설계 방법으로, 대표적으로 memoization 이라고 부르는 테크닉을 사용할 수 있죠. memoization 은 재귀호출의 각 parameter 에 대해 한번 계산 후에는 결과를 저장해 두고, 그 후부터 호출되었을 때는 저장되었던 값을 그냥 리턴하는 방식으로 구현됩니다. 자세한 것은 다음 기회에.. ^^; 위 코드를 memoization 을 사용하도록 바꾸면 다음과 같이 됩니다.

int cache[5000][5000];
int getPrefixLength(const string& s, int a, int b)
{
  if(a == s.size() || b == s.size() || s[a] != s[b]) return 0;
  if(cache[a][b] != -1) return cache[a][b]; // -1 이 아니라면 이미 한 번 계산한 값이라고 봄
  return cache[a][b] = getPrefixLength(s, a+1, b+1) + 1;
}
int main()
{
  ...
  memset(cache, -1, sizeof(cache)); // cache 배열을 -1 로 초기화
  ...
}

이 방법을 이용하면 getPrefixLength() 함수가 모든 a, b 에 대해서 O(1) 의 시간에 동작하기 때문에 O(n^2) 의 시간이 걸립니다. 자세한 시간 복잡도 분석은 약간 복잡하니까 여기서는 생략하고, 다음에 동적 계획법 튜토리얼에서 설명해 보도록 하겠습니다.

(이 방법은 WE ARE BUT MEN, ROCK! 팀에서 사용했다고 하는군요~)

4. Suffix Array 를 이용한 O(n^2lgn) 해법

문 자열 문제를 해결하는데 익숙한 사람들은 자동적으로 이 해법을 떠올렸을 법 한데요, Suffix Array 를 이용한 것입니다. Suffix Array 는, S 의 모든 suffix 를 정렬해서 담고 있는 배열입니다. 예를 들어, "abracadabra" 의 Suffix Array 는

suffixArray[0] = a
suffixArray[1] = abra
suffixArray[2] = abracadabra
suffixArray[3] = acadabra
suffixArray[4] = adabra
suffixArray[5] = bra
suffixArray[6] = bracadabra
suffixArray[7] = cadabra
suffixArray[8] = dabra
suffixArray[9] = ra
suffixArray[10] = racadabra

가 됩니다. 이와 같은 자료 구조는 생물정보학(Bioinformatics) 나 정보검색(Information Retrieval) 같은 분야에서 활발히 연구되고 쓰이고 있죠. 이를 만들기 위한 가장 간단하고 시간이 오래 걸리는 방법은, S 의 각 위치를 가리키는 char* 를 정렬하는 것입니다. 다음과 같이요:

bool cmpChar(const char* a, const char* b) { return strcmp(a, b) < 0; }
void solve2(const string& s)
{
      vector<const char*> suffix;
      for(size_t i = 0; i < s.size(); ++i) suffix.push_back(s.c_str() + i);
      sort(suffix.begin(), suffix.end(), cmpChar);
      // 여기서부터는 생략
}

이렇게 하면, 두번 등장하는 부분 문자열은 반드시 인접해 있기 때문에 p 의 인접한 요소들만을 O(n) 걸려서 비교하면 됩니다. 여기에 O(n^2) 의 시간이 들고 소트에 드는 시간이 O(n^2lgn) 이기 때문에, 전체 시간 복잡도는 O(n^2lgn) 이 되죠.

5. Suffix Tree 를 이용한 O(n^2) 해법

Suffix Tree 는 Suffix Array 처럼 문자열을 다루는 문제에 자주 사용될 수 있는 자료 구조입니다. Suffix Tree 는 S 의 suffix 를 모두 담고 있는 일종의 트라이(trie) 입니다. Trie 는 각 노드가 알파벳의 개수만큼의 자손을 가질 수 있는 트리로, 다음과 같이 생겼습니다. http://en.wikipedia.org/wiki/Image:Trie_example.svg

자세한 것은 따로 공부해 보시고.. ^^;; Trie 를 만들고 거기에 S의 모든 suffix 를 집어넣으면 O(n^2) 의 시간이 걸립니다. 여기서 모든 노드를 순회하면서 2번 이상 나타난 노드들 중 루트에서 가장 먼 것까지의 거리를 기록하면 되겠지요.

6. 궁극의 O(n) 해법

놀랍게도, Suffix Tree 는 n 에 대한 선형시간에 생성할 수 있습니다. 이렇게 하면 Suffix Tree 생성만으로 간단히 O(n) 시간에 이 문제를 풀 수 있게 되죠. 이 알고리즘은 꽤 어렵고 복잡하기 때문에 아마 문제를 출제할 때 이 해법을 요구하지는 않았을 거라고 생각되구요. 자세한 것을 원하시는 분은 열심히 구글링해 보세요~ :D