我试图标记一个字符串.我有一张以trie形式订购的可用代币表.每个令牌都知道它有孩子.一个简单的令牌表看起来像,
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.算法是贪婪的,它会尝试总是找到最长的匹配.
为此,我将开始从输入中读取每个字符,查找匹配项,如果找到匹配项并且令牌具有子项,则通过包含下一个字符再次查找匹配项.这样做直到我们找到最长的匹配.如果未找到匹配项,请尝试匹配包含下一个字符,直到我们到达字符串结尾或成功匹配为止.
如果我们在没有匹配的情况下到达字符串的末尾,则输出?符号并从输入中删除第一个字符.用剩余的字符重复整个过程.
该算法有效,但回溯和迭代所有可能的输入组合使其变得缓慢而复杂.
我想知道有更好的解决方法吗？任何帮助,将不胜感激.
您可以将所有可能的结果保留在内存中，而不是回溯，直到在输入流中的某一点选出一个结果。例子
令牌：S STACK STACKOVERFLOW STAG OVER OVERFLOW
字符串：SSTACKOVERFUN
1 - 在位置 0 上找到 S，有以 S 开头的令牌，尝试全部，只有 S 有效，因此在 1 上解析 S
2 - S，有这样的令牌，尝试它们，可能有效的是 S 和 STACK。不要下定决心，只需记住它们。
3 - T on 2，没有这样的令牌，所以现在可以解析 S，但是我们还有更长的令牌（STACK），所以 S 不好。去掉S，只剩下STACK，但它有孩子。尝试给孩子们用绳子。没有可能的子代，因此在 6 上解析 STACK
4 - O，有这样的标记，尝试它们，只有 OVER，因此在 10 上解析 OVER
5 - F，没有这样的标记，并且之前没有任何可解析的内容，因此这是不可标记的
6 和 7 - 与步骤 5 相同
最终结果：S STACK OVER 乐趣