问您是否使用过KMP或BM算法？

EN

例如，如果你看一下Java的String.indexOf函数，你会发现他们似乎使用暴力方法进行字符串匹配。你可能想知道为什么会这样。

原因是在这些算法中会执行一些查询预处理，这可能会很昂贵(特别是对于同时使用两个数组的BM )。因此，您搜索的字符串必须很大，KMP和BM才能击败暴力破解方法。

当使用不同的算法时，总是有一个折衷的，当处理大字符串时，你可以考虑索引文本而不是查询(例如后缀树)。当你每次处理新的文本时，这甚至可能是有用的。

在我看来，这些算法是相当学术的，只有在特殊情况下才有用。

glibc的strstr函数是线性的。它使用的是Two-Way Algorithm，我认为它是Boyer-Moore的变体。所以，我猜这使得任何在“gcc”中使用strstr的人，在现实世界中实际上都在使用一种快速的字符串搜索算法。

至于快速算法是否重要的问题，我认为只有在数据足够大的情况下才重要。我们所做的很多显式字符串操作都是针对非常小的字符串(比如少于500个字符)。这并不是说我们不做繁重的字符串操作(例如，对数据库进行全文搜索)，但在这种情况下，我们通常会让数据库或库为我们做繁重的工作。数据库或库使用快速字符串搜索算法-所以我不会说它们无关紧要，只是它的使用对我们来说是不可见的。

我在硬件上实现了一次KMP。如果硬件是FPGA，您可以使用可重配置功能来实现自修改电路。此电路获取搜索字符串。然后在硬件中进行必要的预转换，并将其自身重新配置为实际制造KMP的逻辑。但是在这里，你也有必要抓取大量的数据来提高速度，但也有这样的情况(例如DNA匹配)。