Skip to content

Instantly share code, notes, and snippets.

@msg555
Created December 8, 2012 22:04
Show Gist options
  • Save msg555/4242182 to your computer and use it in GitHub Desktop.
Save msg555/4242182 to your computer and use it in GitHub Desktop.
Computes RSK tableau in O(N sqrt(N) log(N)) time
vector<vector<int> > bounded_rsk(const vector<int>& A, int k) {
vector<vector<int> > h(k);
for(int i = 0; i < A.size(); i++) {
int x = A[i];
for(int j = 0; j < k; j++) {
int p = lower_bound(h[j].begin(), h[j].end(), x) - h[j].begin();
if(p == h[j].size()) {
h[j].push_back(x);
break;
} else {
swap(x, h[j][p]);
}
}
}
return h;
}
vector<vector<int> > fast_rsk(vector<int> A) {
int rtn = (int)ceil(sqrt(A.size()));
vector<vector<int> > h_a = bounded_rsk(A, rtn);
reverse(A.begin(), A.end());
vector<vector<int> > h_b = bounded_rsk(A, rtn);
h_a.resize(h_b[0].size());
for(int i = rtn; i < h_b[0].size(); i++) {
for(int j = 0; i < h_b[j].size(); j++) {
h_a[i].push_back(h_b[j][i]);
}
}
return h_a;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment