Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- std::vector<std::pair<int,int>> suffix_array(const std::vector<std::string>& ss) {
- std::vector<std::vector<std::pair<int,int>>> tmp(26);
- size_t n = 0;
- for (size_t i = 0; i < ss.size(); i++) {
- if (ss[i].length() > n) {
- n = ss[i].length();
- }
- for (size_t j = 0; j < ss[i].length(); j++) {
- tmp[ss[i][j] - 'a'].push_back(std::make_pair(i,j));
- }
- }
- // initialize pos
- std::vector<std::pair<int,int>> pos;
- std::vector<bool> bh;
- for (auto &v1 : tmp) {
- bool b = true;
- for (auto &p: v1) {
- pos.push_back(p);
- bh.push_back(b);
- b = false;
- }
- }
- // initialze inv_pos
- std::map<std::pair<int,int>,int> inv_pos;
- for (size_t i = 0; i < pos.size(); i++) {
- inv_pos[pos[i]] = i;
- }
- int H = 1;
- while (H <= n) {
- std::vector<int> count(pos.size(), 0);
- std::vector<bool> b2h(pos.size(), false);
- for (size_t i = 0, j = 0; i < pos.size(); i++) {
- if (bh[i]) {
- j = i;
- }
- inv_pos[pos[i]] = j;
- }
- int k = 0;
- int i = 0;
- while (i < pos.size()) {
- int j = k;
- i = j;
- do {
- auto t = std::make_pair(pos[i].first, pos[i].second - H);
- if (t.second >= 0) {
- int q = inv_pos[t];
- count[q] += 1;
- inv_pos[t] += (count[q] - 1);
- b2h[inv_pos[t]] = true;
- }
- i++;
- } while (i < pos.size() && !bh[i]);
- k = i;
- i = j;
- do {
- auto t = std::make_pair(pos[i].first, pos[i].second - H);
- if (t.second >= 0) {
- int q = inv_pos[t];
- if ((j <= q) && (q < k) && (j <= (q+1)) &&
- ((q+1) < k) && b2h[q+1]) {
- b2h[q+1] = false;
- }
- }
- i++;
- } while (i < k);
- }
- bh = b2h;
- for (auto &x : inv_pos) {
- pos[x.second] = x.first;
- }
- H *= 2;
- }
- return pos;
- }
Add Comment
Please, Sign In to add comment