0

这个问题很复杂,因此请提出问题以解释有关此问题的更多详细信息。(ps。我不是以英语为母语的人,这就是为什么......)

输入是长度为 34 的样本序列,而输出是结果部分

现在,我有一个长度为 34的序列样本,它可以构造为:(“结果”是我需要的)

样本序列=结果部分+已知序列(我不知道结果部分的长度

  1. 结果(长度 34)
  2. 结果(长度 N,N < 34)+已知序列(34 - N)

所有这些按顺序排列的数字都是随机的。

现在,我需要找到不包括序列已知部分的结果部分。

一些背景资料:

  1. 我有 1000 万个长度为 34 的样本序列。(来自生成器的 1000 万个知道 34 位随机数序列)

  2. 找到结果后,我需要在 500 万长度的序列B上进行比较,并查找结果序列是否在某处的长序列上唯一匹配。

我目前的算法是使用一个检测器,它是已知序列的前 10 位数字,如果我在样本序列的某处检测到检测器序列,则删除该序列但是,结果仍然有可能包含已知序列内的序列部分。有没有人有更好的算法?

非常感谢!另外,我在 python 下对此进行了编程。

前任。

第一个条件

199010104761700150004736290473629657 == 样品序列

都是结果,已知部分仍然相同

输入:

199010104761700150004736290473629657

输出:

199010104761700150004736290473629657

第二个条件

199010104728392817111123995561547659 == 样品序列

1990101047 == 结果部分

28392817111123995561547659... == 已知部分

输入将是:199010104728392817111123995561547659, 28392817111123995561547659 ...

我想要的输出是:1990101047

4

1 回答 1

1

您可以使用Knuth–Morris–Pratt 算法。您实际上不会找到子字符串,但您可以记下i到达主题字符串末尾时的值。

于 2012-06-19T09:47:46.533 回答