你曾经使用过KMP或BM算法吗?

use*_*656 4 algorithm

我知道KMP(Knuth-Morris-Pratt)和BM(Boyers-Moore)算法都是很好的字符串搜索操作算法.我也知道BM比KMP快3-5倍.

根据您的行业软件编程经验,您是否使用过BM或KMP算法?这个算法真的很重要吗?

jal*_*mer 6

如果您查看Java的String.indexOf函数,它们似乎使用强力方法进行字符串匹配.你可能想知道为什么会这样.

原因是某些查询预处理在这些算法中执行,并且可能成本很高(特别是对于BM,如果您同时使用这两个数组).因此,在KMP和BM可以使用暴力方法之前,您搜索的字符串必须是大的.

总是存在使用不同算法的交易,当处理大字符串时,您可以考虑索引文本而不是查询(例如后缀树).当您每次处理新文本时,这甚至可能很有用.

在我看来,这些算法相当具有学术性,只有在特殊情况下才有用.

  • 有趣的是,gcc`strstr()`实现(相当于`String.indexOf()`)使用非常酷的算法,只需要线性时间,与BM和KMP不同,*常量空间*.这基本上消除了在库函数中使用朴素O(n ^ 2)方法的任何理由,因为唯一的情况是它将更快是在极短的字符串上,其中两个算法已经非常(即足够)快.(从MAK的回答中得到了这个.) (2认同)