对于类主题,我必须实现一个类,该类在该类按时间顺序接收的字符集中寻找模式。类收到的每个字符都有一个特定的来源(一个行星,由一个int ID标识)。
我们必须自己实现数据结构,因此我实现了一个字符串列表,在其中按时间顺序存储所有这些字符。
问题在于,必须为来自相同行星(来源)的字符匹配模式,因此必须在每个来源上进行模式匹配。
我尝试通过浏览整个列表并仅考虑当前浏览的源,然后对所有源进行此操作来使用诸如Rabin Karp之类的著名模式匹配算法,但是性能确实很差,甚至比幼稚的(甚至同步)还差。 )解决方案。
您是否知道在那种情况下哪种算法可能更有效? (让我使用我正在浏览的每个字符,即使这意味着将该源的实际“搜索状态”存储在某个地方,就像我们为朴素的实现所做的一样)
P.S:ID是有限的(从1到128),但字符数最多可以达到10个字符
编辑:以下是一些详细信息,希望可以澄清这些内容。IntlFinder
,我的类(class),可以通过Add(char* pszData, int nSource)
方法接收字符(或字符数组);因此,每个字符都带有一个源ID。该对(字符,源)存储在StringList ComList
中(按其添加的时间顺序)。
为了使该模式出现在我的类(class)中,必须在THE SAME SOURCE中出现。
例:
如果我正在寻找SAYKOUK模式
( S ,1); ( A ,1); ( Y ,1); ( K ,1); (Z,2); (S,3); ( O ,1); ( U ,1); ( K ,1)
还行吧!
( S ,1); ( A ,1); ( Y ,1); (K,2); (O,3); (U,1); (K,4)
不好
这是有问题的,因为如果我仅考虑一个来源(范围从1到128),并且每次都浏览整个列表,则我的模式搜索方法的确非常慢。而且,我无法使用这些算法中的任何一种来考虑不同来源的特征,并且在我遇到任何一种算法时都知道!
最佳答案
解决方案是为每个源存储一个单独的字符列表,然后在这些列表中分别找到模式。
关于c++ - 多个串联字符串的同步模式匹配算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/12795542/