c++ - 后缀数组算法实现
问题描述
我目前正在尝试根据本文描述的算法实现广义后缀数组: paper。然而,我现在被第 2 章中排序算法的实现困住了。我当前的 c++ 代码大致如下(我的字母表是小写英文字母):
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(bh);
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;
}
目前,我的实施得到了垃圾结果。而且我不太了解论文中的算法描述如何inv_pos
在每个阶段之后正确更新......如果有人能发现我的实现有什么问题并通过简短的解释告诉我正确的方向,我将非常感激。
解决方案
推荐阅读
- elasticsearch - 如何忽略 kibana 查询中突出显示的字段?
- c++ - 即使使用正确的键,QMap 也会返回空值(键具有相同的地址:不可能不正确吗?)
- google-cloud-platform - 如何在 Google Cloud SQL 2nd Gen 上跳过从属复制错误
- android - 对返回 when 语句感到困惑
- java - 如何将 WAR 文件部署到 Wildfly?
- bash - 无法从 azure 管道 Git 推送到远程分支(非主分支)
- python-3.x - Python3 - 从文本文件中删除一行时出现问题
- python - 有没有办法将python中的多行字符串解析为列表列表
- node.js - 我在 Heroku 上部署了我的应用程序,但是当我在数据库中添加条目时看不到图像。什么是正确的路径?
- swift - 在 Swift 中不使用 case 语句从错误枚举中获取消息