HABIT 시간초과

  • yongwhan
    yongwhan

    알고리즘 문제해결전략에 있는 풀이를 보고 코드를 작성하였는데 시간초과가 떠서 질문드립니다. 혹시 제가 잘못 작성한 부분이 있는지요? 참고로 책에서는 vector group을 const vector &group으로 작성했는데 그렇게 하면 다음과 같은 에러가 떠서 그렇게 못했습니다.

    error: passing ‘const std::vector’ as ‘this’ argument of ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator]’ discards qualifiers [-fpermissive]
    group=_group;

    또 cin/cout을 scanf/printf로 바꾸었는데도 시간초과가 뜨네요..

    해결책을 알려주세요. 감사합니다!

    #include<bits/stdc++.h>
using namespace std;

struct Comparator {
  vector<int> group;
  int t;
  Comparator(const vector<int> &_group, int _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];
  }
};

vector<int> getSuffixArray(const string &s) {
  int n=s.size();
  int t=1;
  vector<int> group(n+1);
  for (int i=0; i<n; i++) group[i]=s[i];
  group[n]=-1;
  vector<int> perm(n);
  for (int i=0; i<n; i++) perm[i]=i;
  while(t<n) {
    Comparator compareUsing2T(group, t);
    sort(perm.begin(), perm.end(), compareUsing2T);
    t*=2;
    if(t>=n) break;
    vector<int> newGroup(n+1);
    newGroup[n]=-1;
    newGroup[perm[0]]=0;
    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=newGroup;
  }
  return perm;
}

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;
}

int longestFrequent(int k, const string &s) {
  vector<int> a=getSuffixArray(s);
  int ret=0;
  for (int i=0; i+k<=s.size(); i++)
    ret=max(ret, commonPrefix(s, a[i], a[i+k-1]));
  return ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int t; cin>>t;
  while(t--) {
    int k; string s; cin>>k>>s;
    cout << longestFrequent(k,s) << endl;
  }
  return 0;
}


    8년 전
1개의 댓글이 있습니다.
  • WeissBlume
    WeissBlume

    struct Comparator {
    const vector& group;
    const int t;
    Comparator(const vector &group, int t):
    group(group), t(t) {}
    // 생략
    };

    reference 변수는 반드시 생성과 동시에 초기화돼야 합니다.
    따라서 = 연산자로 대입하는 게 아니라 위와 같이 생성자에 넣어줘야 합니다.


    8년 전 link

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