整数序列在线百科全书支持搜索包含您的查询作为子序列的序列，例如:搜索subseq:212,364,420,428将返回8*n+4序列。(http://oeis.org/search?q=subseq: 212364420428)
这个惊人的功能显然是由Russ Cox通过http://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Features实现的，但它没有指定实现的算法。
我想知道这是怎么做的。显然，对于搜索引擎来说，每次搜索都要经过近一百万个序列是不切实际的。只是保持第一个数字的索引(这就是相同的Russ Cox做Google Code Regex搜索的方式)和暴力强迫其余的也不起作用，因为像0这样的数字几乎在所有序列中。事实上，像0 1这样的查询在整个数据库中匹配的百分比很高，因此该算法需要对所需输出大小的运行时间敏感。
有人知道这个功能是如何实现的吗?
我猜部分数据存储在倒排索引中。也就是说，每个数字都链接到一组序列，当输入多个序列时，将显示公共序列的集合。这是非常快的，几乎所有的搜索引擎使用。
作为后缀树或任何链接数据结构存储在此应用程序中是无用的。
至少对于一些序列集(例如ax+b)，我认为最好将它们参数化保存，而不是存储实际序列。
首先，在线搜索似乎只适用于1000以内的数字。它也适用于更大的数字吗?其次，出于好奇，对于您提供的示例，由于某种原因，OEIS没有列出A000027，这只是自然数，但显然应该匹配。
数据库解决方案
如果这是纯粹在DB中实现的，对于一个4项搜索，它将是这样的:
<<p> 表/em>sequence {seqid, seqname等}
seqitem {value, seqid, location}
查询选择si1。ds, si1。位置,si2。位置……从seqitem si1, seqitem si2, seqitem si3, seqitem si4si1的地方。Seqid = si2。Seqid和si2。Seqid = si3。Seqid和si3。Seqid = si4.seqid和si1。位置& lt;si2。位置和si2。位置& lt;si3。位置和si3。位置& lt;si4.location和si1。价值=$v1和$ si2。Value = $v2和$ si3。价值= $v3和$ si4。Value = $v4