c - 标记字符串的有效方法 - C

Question

我正在尝试标记一个字符串。我有一个以 trie 形式排序的可用 token 表。每个 token 都知道它有 child 。一个简单的标记表看起来像，

pattern    value         has_children
--------   ------        --------
s          s-val         1
stack      stack-val     0
over       over-val      1
overflow   overflow-val  0

在此表中，stack 是s 的子元素，overflow 是over 的子元素。实际上，该表将有 5000 多条以这种方式排序的记录。

现在，给定一个字符串 stackover，它应该输出 stack-valover-val。算法是贪心的，它总是会尝试找到最长的匹配。

为此，我将开始从输入中读取每个字符，查找匹配项，如果找到匹配项并且标记有子项，则通过包含下一个字符再次查找匹配项。这样做直到我们找到最长的匹配。如果未找到匹配项，则尝试通过包含下一个字符进行匹配，直到到达字符串末尾或成功匹配。

如果我们到达字符串末尾但没有匹配项，则输出 ? 符号并从输入中删除第一个字符。对剩余字符重复整个过程。

此算法有效，但对所有可能的输入组合进行回溯和迭代使其变得缓慢而复杂。

我想知道是否有更好的方法来解决这个问题？任何帮助，将不胜感激。

Answer 1

您可以将所有可能的结果保存在内存中，而不是回溯，直到一个结果在输入流中的特定点出现。示例

代币:S STACK STACKOVERFLOW STAG OVER OVERFLOW
字符串:SSTACKOVERFUN

1 - 在位置 0 找到 S，有以 S 开头的标记，全部尝试，只有 S 有效，所以解析 S
2 - S on 1，有这样的标记，试试看，可能有效的是 S 和 STACK。不要解决，只要记住它们。
3 - T on 2，没有这样的标记，所以现在可以解析 S，但是我们还有更长的标记 (STACK)，所以 S 不好。抛弃 S，只剩下 STACK，但它有 child 。为 children 尝试字符串。没有可能的 child 所以解决STACK
4 - O on 6，有这样的标记，尝试它们，只有 OVER，所以解决 OVER
5 - F on 10，没有这样的标记，之前也没有什么要解决的，所以这是不可标记的
6 和 7 - 与步骤 5 相同

最终结果:S STACK OVER fun