알고리즘 문제해결전략에 있는 풀이를 보고 코드를 작성하였는데 시간초과가 떠서 질문드립니다. 혹시 제가 잘못 작성한 부분이 있는지요? 참고로 책에서는 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로 바꾸었는데도 시간초과가 뜨네요..

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

~~~ c++
#include
using namespace std;

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