(21162) 뒤집기 K

https://www.acmicpc.net/problem/21162

단계별로 풀어보기

46단계(문자열 알고리즘 1) 8번째

 

 

 

길이가 같은 두 문자열의 사전 순 비교를 나이브하게 하는 법은 첫 글자부터 비교하여 O(N)이 걸린다. 하지만 해싱을 이용하면 O(log N)으로 사전 순 비교를 할 수 있다.

해싱을 이용하면 두 문자열이 같은지 확인하는 연산을 O(1)에 할 수 있다. 파라메트릭 서치를 이용해 비교 함수는 부분문자열 A[:mid]와 B[:mid]가 같은 값인가?로 설정하면 이 연산은 O(1)이므로, 두 문자열을 비교했을 때 처음으로 값이 달라지는 위치를 O(log N)으로 찾을 수 있다. 이 인덱스의 문자를 비교하는 건 O(1)이므로 결과적으로 한 번의 사전 순 비교를 O(log N)에 할 수 있다.

따라서 문자열의 집합의 정렬을 O(N log N)*O(log N)= O(N log^2 N)에 할 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define p 524287
#define mod 998244353

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n >> k;
  
  vector<int> v(n), str(n-1);
  vector<long> hash(2*n-1), base(2*n-1);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  for(int i=0;i<n-1;i++)  str[i]= i+1;
  
  reverse(v.begin(), v.end());
  v.insert(v.end(), v.begin(), v.end());
  
  base[0]= 1;
  for(int i=1;i<2*n-1;i++){
    hash[i]= (hash[i-1] * p + v[i]) % mod;
    base[i]= (base[i-1] * p) % mod;
  }
  
  auto gethash= [&](int l, int r) -> long {
    return (hash[r]-(hash[l-1]*base[r-l+1]%mod)+mod)%mod;
  };
  
  sort(str.begin(), str.end(), [&](int A, int B){
    int l= 0, r= n;
    
    while(l<r){
      int mid= (l+r)/2;
      
      long a= gethash(A, A+mid), b= gethash(B, B+mid);
      
      if(a==b)  l= mid+1;
      else  r= mid;
    }

    if(l==n)  return false;
    return v[A+l] < v[B+l];
  });
  
  for(int i=str[k-1],j=0;j<n;j++){
    cout << v[i+j] << " ";
  }
  
  return 0;
}