5개의 댓글이 있습니다.

• 
  wookayin

  • 첫 네글자라는것은, 앞의 4글자를 본다는 뜻입니다.
    코드를 보시면 이해가 되시겠지만, a[0:4], b[0:4] 를 비교하는 것이므로 차례대로 0번째 글자, 1번째 글자, 2번째 글자, 3번째 글자를 비교하는 게 되겠지요.

  • 그래서 3번째 글자는 어쨌거나 봐집니다. sipi가 sissipi보다 앞으로 정렬된 것은 (h=4일 때까지 iteration을 돌았을 때), 세번째 글자를 이미 보았기 때문이기도 합니다. 다음 iteration에서는 각 suffix마다 앞 8글자 (1번, 8번만 보는게 아님, 길이 8) 를 보고 정렬을 하겠죠.

  
  9년 전 link

• 
  cjkis

  하지만 666페이지 sort에서 사용한 구조체 비교 함수를 보면

  struct Comparator {
  const vector& group;
  int t;

  Comparator(const vector<int>& _group, int _h) : group(_group), t(_h) { }
  
  bool operator () (int a, int b) {
      // 첫 t 글자가 다르면 이들을 이용해 비교한다
      if (group[a] != group[b]) return group[a] < group[b];
      // 아니라면 S[a+t..] 와 S[b+t..] 의 첫 t 글자를 비교한다
      return group[a + t] < group[b + t];
  }

  };

  에서 정렬시에 사용하는 operator() 함수에서는 group[a] group[b]를 비교 한 후에 중간값 비교없이 바로 t를 더해서 group[a + t] < group[b + t] 결과만을 리턴해버리는데용...
  저런식으로하면 1+1, 1+2, 1+4, 1+8, 1+16 과같은 식으로되서 중간에 있는 값들의 비교는 안하는것 아닌가횻?

  
  9년 전 link

• 
  wookayin

  네, 사실 이 부분이 바로 이 알고리즘의 핵심(doubling technique 라고 하나요?)입니다. 루프를 돌면서 앞 2^k$2^k$ 글자들을 다 비교하면 시간복잡도가 너무 커지죠.

  저 comparator가 사용되는 시점에 (sort 함수가 호출될 때), group 이라는 배열값은, 앞의 h$h$글자를 갖고 suffix들을 비교했을 때의 순서를 반영합니다 (엄밀하게 말하면, group[a] < group[b] 와 string[a:a+h] < string[b:b+h] 가 동치입니다).

  이 comparator를 써서 sort 를 하는 목적은, 앞의 2h$2h$글자들을 갖고 suffix를 비교했을 때의 순서를 만들기 위함이기 때문에,

  • 앞쪽 h$h$글자를 비교 : string[a:a+h], string[b:b+h] 를 비교 (group[a], group[b]를 비교)
  • 뒤쪽 h$h$글자를 비교 : 앞의 비교 결과가 같다면, string[a+h:a+2h], string[b+h:b+2h] 를 비교

  를 하는 겁니다. 이렇게 하면, 이전의 group 계산 결과를 통해 O(1)$O(1)$ 만에 길이 2h$2h$에 대해서도 비교 및 정렬을 할 수 있습니다. 그러니까, 지적하신 중간 부분에 대한 건, 이미 group 이라는 값에 인코딩 되어 있다고 보시면 아마 헷갈렸던 부분을 바로잡으실 수 있을것 같습니다.

  .. 라고 책에 설명이 나와있는 것으로 기억하는데 제 옆에 지금 책이 없어서 그냥 머리속에 떠오르는대로 설명을 적어 보았습니다. 도움이 되시길 바랍니다 :)

  
  9년 전 link

• 
  JongMan

  wookayin님의 설명은 역시 정확하십니다.

  
  9년 전 link

• 
  arubirate

  좋은 설명 감사합니다. :D

  
  8년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.