c++ - 相同模式多次出现的 Horspool 算法

Question

我已经在 C++ 中实现了 Horspool 算法（取决于Anany Levitin的算法设计和分析简介，第 2 版，第 258 页），用于查找文本中所需模式的第一次出现的位置。但是，我想扩展算法以查找相同模式的多次出现。不幸的是，我被困在后一种实现上。你可以在下面看到我的代码：

该函数计算并返回所需模式在文本中第一次出现的位置。移位大小存储在 ShiftTable 中，并且 ShiftTable 由所需字母表的字符索引。此外，整数计数器用于计算模式和文本字符之间的总比较。计数器最初具有零值。我如何扩展它以找到相同模式的多次出现？

我在 main() 函数的主体中尝试了以下操作，但它虽然有效，但它不是有效的。如果遇到第一次出现的模式，它的位置将被打印，并且以第一次出现的模式结束的文本部分将被删除。此外，该程序将检查模式等的剩余文本。

int counter=0;
while ((position = Find(pattern,text,ShiftTable,counter)) != -1) {
    cout << position << endl;
    text = text.erase(0,result+m);
}

有任何想法吗？

score 2 · Accepted Answer

目前，您总是从头开始 ( i = m - 1)。如果你想恢复之前的搜索，只需传入最后一个开始的位置。

在下文中，我删除了counter变量 - 无论如何它有什么用？

int Find(string pattern, string text, int *ShiftTable, int start = 0)

……和……</p>

i = start + m - 1,

......只需按如下方式调用代码：

while ((position = Find(pattern,text,ShiftTable,position)) != -1)  {
    cout << position << endl;
    ++position;
}

1 回答 1