Online Dictionary Matching with One Gap

The Online Dictionary Matching with Gaps Problem (DMG), is the following. Preprocess a dictionary $D$ of $d$ gapped patterns $P_1,ldots,P_d$ such that given a query online text $T$ presented one character at a time, each time a character arrives we must report the subset of patterns that have a match ending at this character. A gapped pattern $P_i$ is of the form $P_{i,1}{alpha_i,eta_i}P_{i,2}$, where $P_{i,1},P_{i,2}in Sigma^*$ and ${alpha_i,eta_i}$ matches any substring with length between $alpha_i$ and $eta_i$. Finding efficient solutions for DMG has proven to be a difficult algorithmic challenge. Little progress has been made on this problem and to date, no truly efficient solutions are known. In this paper, we give a new DMG algorithm and provide compelling evidence that no substantially faster algorithm exists, based on the Integer3SUM conjecture.

在线带间隔字典匹配问题（DMG）如下。对包含$d$个带间隔模式$P_1,\ldots,P_d$的字典$D$进行预处理，使得对于每次逐个字符给出的在线查询文本$T$，每当一个字符到达时，我们必须报告以该字符结尾匹配的模式子集。一个带间隔模式$P_i$的形式为$P_{i,1}\{\alpha_i,\beta_i\}P_{i,2}$，其中$P_{i,1},P_{i,2}\in\Sigma^*$，并且$\{\alpha_i,\beta_i\}$匹配任何长度在$\alpha_i$和$\beta_i$之间的子串。为DMG找到高效的解决方案已被证明是一个困难的算法挑战。在这个问题上进展甚微，到目前为止，还没有已知的真正高效的解决方案。在本文中，我们给出了一种新的DMG算法，并基于整数3SUM猜想提供了令人信服的证据，表明不存在实质上更快的算法。