java - 在长字符串中查找模式？

Question

我有 40KB 的 HTML 页面，我想在其中找到某些模式。

我可以通过 1K 缓冲区读取它，但我想避免我正在搜索的模式被分成两个缓冲区读取的情况。

如何克服这个问题？

Answer 1

这很简单。您计算要查找的最长模式，然后按该长度回溯文件指针，或者滚动文件，只读取增量。

想象一下最长的模式是 26 个字节。

1. 阅读 1k。
2. 检查所有模式 -> 无。
3. 从缓冲区中删除 1k - 26 字节。
4. 从流中读取 1k - 26 字节并添加到您的缓冲区
5. 转到 2。

编辑:让我澄清一下:有两种方法可以做到这一点，两者各有千秋。如果您正在从流中读取，这意味着不支持搜索的数据源，那么我上面记录的那个是最好的。但是，如果您的数据源确实支持查找(如文件系统文件)，您可以轻松地对查找进行同样的操作。检查模式，如果没有找到，请返回最长模式的大小，然后从那里开始。

但是，如果您希望支持搜索比缓冲区大小更长的模式，您可能需要更聪明的算法。当您继续读取更多数据时，您将需要一个包含当前“打开”的所有模式的查找表，这反过来会消耗更多内存 - 您会遇到问题。