基于散列的串匹配方法及其选择模式串子窗口的方法

摘要

本发明提供一种基于散列的串匹配方法及其选择模式串子窗口的方法。通过选择每个模式串的最优子窗口来计算该模式串的散列值，并以此来建立散列表。从而在大量的模式串有相同的前缀、后缀或子串的情况下，确保模式串尽量均匀地散列到散列表中，提高散列表的均匀性，保证基于散列的串匹配方法的高效运行。

主权项

一种用于基于散列的串匹配中的选择模式串子窗口的方法，所述方法包括：步骤1)求得模式串集合中最短模式串长度m；步骤2)对于模式串集合中的每个模式串，计算其所有长度为m的子串的散列值，组成散列值集合；步骤3)确定所述模式串集合与所述散列值集合中的元素的一一对应关系，所述对应关系应满足模式串所对应的散列值是根据该模式串的一个长度为m的子串计算出散列值，同时将这个子串设置为该模式串的子窗口。