安全破解澳大利亚信息学奥林匹克2009年Intermedi

Question

嗨，最近我在尝试AIO 2009中级考试的一个问题。在

问题在于：

有一个正整数序列，每个正整数都通过一个非负常量k（通过将k加到序列中的每个值上，并且只要a和b的以下边界保持不变，k就没有边界），从而得到一个整数列表a。我们得到了原始非加密列表b的一个小子集，使得2<；=len（b）<；=30和2<；=len（a）<；=100000。给定两个列表a和b，编写一个函数，返回原始的非加密整数列表（a和b中的所有整数都满足1<；a，b<；1000000）。我们确信只有一种独特的解决办法。在

我考虑的一些想法是：

对b的所有可能的组合进行暴力破解，直到找到a的子集（虽然（O（n^2）），但我的解决方案的时间复杂度太高了，如果有人能编写一个O（n）解决方案，它就可以工作了）

求a和b的差，然后求a和b的差。然后我们用这个方法找到b[0]对应的索引，然后得到键k（除了有一些我无法解决的角点情况外，这个方法有效）

我想知道是否有人可以在python3.x中使用这两种方法中的任何一种来编写解决方案。另外，你能解释一下哪种方法更好更有效吗？为什么？在

谢谢

Answer 1

假设您得到以下“加密”整数列表：

E1 = [200,450,100,75,275,500,600,400,300]

以及解密的子列表。如下所示：

^{pr2}$

将L1转换成一个新的数组L2，这样每个元素都是它自己和前一个元素之间的区别。即L2[i] = L1[i] - L1[i-1]。对于L2[0]，设为零。在

L2 = [0,200,225,100,-200]

删除第一个元素（L2 = L2[1:]）

^{4}$

现在，对加密列表执行相同的规范化操作：

E2 = [250,-350,-25,200,225,100,-200,-100]

现在在规范化列表上执行一个经典的子字符串搜索，以查找L2从E2开始的匹配索引。在

def findStartIndex(needle, haystack):
    j = 0
    while len(needle) < len(haystack[j:])
         if (needle == haystack[j:j+len(needle)]
             return j
         j = j + 1
    return -1

index = findStartIndex(L2, E2)

如果上面的搜索返回一个整数值：index（在本例中是3）：

那么键k就是：E1[index] - L1[0]

在这个例子中，k是50