c++ - 多个连接字符串的同步模式匹配算法

Question

对于类主题，我必须实现一个类，该类在类按时间顺序接收的一组字符中查找模式。该类收到的每个字符都有一个特定的来源(一个行星，由一个 int ID 标识)。

我们必须自己实现数据结构，所以我实现了一个字符串列表，其中我按时间顺序存储所有这些字符。

问题是模式必须匹配来自同一个行星(源)的字符，因此必须在每个源上进行模式匹配。

我尝试使用像 Rabin Karp 这样著名的模式匹配算法，通过浏览整个列表并只考虑当前浏览的源，然后对所有源都这样做，但是性能真的很差，甚至比天真还差(但同步)解决方案。

在这种情况下，您是否知道哪种算法更有效？ (让我使用我正在浏览的每个字符，即使这意味着将该源的实际“搜索状态”存储在某处，就像我们为天真的实现所做的那样)

P.S:ID 是有限的(从 1 到 128)，但字符数最多可以达到 10⁷

编辑:这里有一些细节，希望能澄清一些事情。

IntlFinder，我的类，可以通过 Add(char* pszData, int nSource) 方法接收字符(或字符数组)；因此，每个字符都与一个源 ID 相结合。这对 (character, source) 存储在 StringList ComList 中(按添加的时间顺序)。

要使模式出现在我的类里面，它必须出现在同一个源中。

例子:

如果我正在寻找模式 SAYKOUK

(S, 1); (A, 1); (Y, 1); (K, 1); (Z, 2); (S, 3); (O, 1); (你, 1); (K, 1)可以!

(S, 1); (A, 1); (Y, 1); (K, 2); (O, 3); (U, 1); (K, 4)不行。

这是有问题的，因为如果我只考虑一个来源(范围从 1 到 128)并且每次浏览整个列表，我的模式搜索方法真的很慢。而且我无法使用这些算法中的任何一种来考虑不同来源的特征，也无法知道何时我遇到了我的模式!

Answer 1

解决方案是为每个源存储一个单独的字符列表，然后分别在这些列表中查找模式。