c - 连续扫描流缓冲区中字符串的最佳方法

Question

我有这种情况，我的函数不断接收各种长度的数据。数据可以是任何东西。我想找到在此数据中寻找特定字符串的最佳方法。该解决方案需要以某种方式缓冲以前的数据，但我无法解决这个问题。

这是问题的一个例子:

数据输入 -> [\x00\x00\x01\x23B][][LABLABLABLABLA\x01TO][KEN][BLA\x01]...

如果每个 [...] 代表一个数据 block ，而 [] 代表一个没有任何项目的数据 block ，那么扫描字符串 TOKEN 的最佳方法是什么？

更新:我意识到这个问题有点复杂。 [] 不是分隔符。我只是用它们来描述上面例子中 block 的结构。 TOKEN 本身也不是静态字符串。它是可变长度的。我认为逐行读取的最佳方法，但问题是如何将可变长度的流缓冲区读入行。

Answer 1

最简单的TOKEN搜索方式是:

• 尝试从流中的位置 0 开始匹配“TOKEN”
• 尝试从流中的位置 1 开始匹配“TOKEN”
• 等等

因此，您需要缓冲的只是流中等于“TOKEN”长度的字节数(5 个字节，或者实际上是 4 个字节)。在每个位置尝试匹配“TOKEN”，这可能需要等到至少有 5 个字节读入缓冲区。如果匹配失败，则倒退到开始匹配的位置，再加一。由于您倒回的长度永远不会超过您正在搜索的字符串的长度(减去一个)，这就是您真正需要的所有缓冲区。

接下来的技术问题是，当您从流中连续读取时，如何维护 5 个字节的缓冲数据。一种方法是所谓的“循环缓冲区”。另一种方法，尤其是在 token 很小的情况下，是使用更大的缓冲区，并且每当您离末尾太近时，将您需要的字节复制到开头并重新开始。

如果您的函数是一个回调函数，为每个新数据 block 调用一次，那么您将需要从一个调用到下一个调用保持某种状态，以允许跨越两个 block 的匹配。如果幸运的话，那么您的回调 API 包含一个“用户数据指针”，您可以将其设置为指向您喜欢的包含缓冲区的任何结构。如果没有，您将需要全局或线程局部变量。

如果流的数据速率很高，那么您可能需要考虑使用 KMP 算法或其他方式加快速度。