可能导致错误的转角情况

Question

最近我在试一些过去一年的所有问题，但我解决不了这个问题。你知道吗

问题如下：

安全开裂 输入文件：safein.txt文件 输出文件：安全输出.txt 时限：1秒 几个世纪以来，许多战争都取得了胜利，不是通过力量之战，而是通过智慧之战。你的消息来源最近告诉你，你母亲已经购买了最新电脑游戏《喘息》的预发行版，并把它藏在家里的保险箱里。要打开保险箱，必须按正确顺序转动圆形表盘，输入一长串数字。你知道吗

如果在保险箱中输入正确的数字顺序，保险箱就会打开，你可以提前把圣诞礼物偷偷带出去。如果你得到的顺序错误的报警系统被激活，你将终身停飞！幸运的是，你知道你妈妈已经把密码写在她床边抽屉里的一张纸上，她喜欢称之为“密码纸”。你知道吗

她经常夸耀自己有多聪明，并向你解释说，表上的数字确实是保险柜的密码，但是序列中的每个数字都增加了一个常数非负整数k，只有她知道。没有这个值，床单就没用了，只有她才能打开保险箱。。。或者她是这么想的！你知道吗

为了确定正确的密码，你在你母亲打开保险箱的时候监视了她，你设法记住了她输入的部分密码。您不确定它对应于代码的哪一部分，但它肯定是代码中连续的数字序列。掌握了这些知识后，您就可以着手确定保险箱的完整代码了。你知道吗

你的任务是，考虑到你母亲写在密码表上的完整数字列表，以及你知道的实际密码中出现的较短序列，确定打开保险箱的整个序列。你知道吗

例如，如果保险箱的密码是7、9、4、6、8、12，而你母亲将所有数字加4，那么她的密码表将显示11、13、8、10、12、16。这是因为7+4=11，第一个数字是11。第二个数字是9+4=13相加得到的。第三个数字是通过4+4=8相加得到的，依此类推。你可能瞥见她按顺序输入数字4、6、8。有了这些知识，您可以确定整个代码。你知道吗

输入 输入文件的第一行将包含两个整数a b，用空格分隔。整数a是写在母亲代码表上的序列长度（2<；=a<；=100000）。整数b是您知道的包含在到保险箱的代码中的序列的长度（2<；=b<；=30）。你知道吗

接下来是一行，每行包含一个1到1000000之间的整数。这些行是写在你母亲密码表上的顺序，按照它们进入保险箱的顺序。你知道吗

接下来是b行，每行包含一个整数，也在1到1000000之间。这些行描述了对保险箱的实际代码的一瞥。你知道吗

您可以保证，对于任何给定的输入场景，只有一个可能的解决方案。你知道吗

输出 输出文件应该由一行组成。每一行都应该包含一个整数，表示打开保险箱所需的完整数字序列。你知道吗

我的代码（通过大多数测试用例）如下：

'''program implements a function diff which is returns a list that is the difference of the current elements in the list
to solve the problem, the subset list is reduced until it consists of a single integer
the index of this integer in the original list is then found, before determining the non-negative integer
which was used to encode the numbers'''
def diff(lst):
    lst2=[]
    for i in range(len(lst)-1):
        lst2.append(lst[i+1]-lst[i])
    return lst2
infile = open("safein.txt", "r")
outfile = open("safeout.txt", "w")
a, b = map(int, infile.readline().split())
lst, sub = [], []
for i in range(a):
    lst.append(int(infile.readline()))
for j in range(b):
    sub.append(int(infile.readline()))
temp_sub=sub
temp_lst=lst
k = 0
while len(temp_sub) != 1:
    temp_sub=diff(temp_sub)
    k+=1
for x in range(k):
    temp_lst=diff(temp_lst)
n = temp_lst.index(temp_sub[0])
m = lst[n]-sub[0]
lst=[x-m for x in lst]
for i in lst:
    outfile.write(str(i) + "\n")

由于此代码通过了大多数测试用例，除了一些给出错误的用例（我不知道它是什么错误），我想知道是否有人可以建议一些可能导致此算法产生错误的角落用例。到目前为止，我想到的所有案子都通过了。你知道吗

编辑： 正如niemmi在下面指出的，我的上述算法不能处理一些副作用。因此，我重写了另一个算法来解决它。该算法通过了大多数t没有错误，只是执行时间超过1s。有人能帮助降低此解决方案的时间复杂性吗？你知道吗

def subset(lst1, lst2):
    if lst2[0] in lst1:
        idx = lst1.index(lst2[0])
        for i in range(len(lst2)):
            if lst2[i]==lst1[idx+i]:
                continue
            else:
                return False
    else:
        return False
    return True

infile = open("safein.txt", "r")
outfile = open("safeout.txt", "w")

a, b = map(int, infile.readline().split())
lst, sub = [], []
for x in range(a):
    lst.append(int(infile.readline()))
for y in range(b):
    sub.append(int(infile.readline()))

if subset(lst, sub):
    for i in range(a):
        outfile.write(str(int(lst[i])) + "\n")
    infile.close()
    outfile.close()
    exit()

i=1
while True:
    temp_sub = [x+i for x in sub]
    if subset(lst, temp_sub):
        lst = [x-i for x in lst]
        for j in range(a):
            outfile.write(str(int(lst[j])) + "\n")
        infile.close()
        outfile.close()
        exit()
    i+=1

编辑： 感谢niemmi，他在下面提供了一个解决方案，我稍微编辑了一下，通过了一个返回错误的测试用例。你知道吗

def diff(seq):
    return (seq[i - 1] - seq[i] for i in range(1, len(seq)))


with open('safein.txt') as in_file:
    a, b = (int(x) for x in in_file.readline().split())
    code = [int(in_file.readline()) for _ in range(a)]
    plain = [int(in_file.readline()) for _ in range(b)]

code_diff = tuple(diff(code))
plain_diff = tuple(diff(plain))

k = 0
def index(plain_diff, code_diff, plain, code, a, b, k):
    for i in range(k, a - b):
        for j, x in enumerate(plain_diff, i):
            if code_diff[j] != x:
                break
        else:
            k = code[i] - plain[0]
            break # found match, break outer loop
    return k

k = index(plain_diff, code_diff, plain, code, a, b, k)

with open('safeout.txt', 'w') as out_file:
    out_file.write('\n'.join(str(x - k) for x in code))

谢谢！你知道吗

Answer 1

上述实现重复计算以下行上连续元素的差异：

while len(temp_sub) != 1:
    temp_sub=diff(temp_sub)
    k+=1

当在第一轮temp_sub之后对示例输入运行时，它是[2, 2]，在第二轮和最后一轮之后，它是[0]。然后实现继续对temp_lst执行相同的缩减，该缩减包含增量代码，从而导致[-7, 7, 0, 2]。你知道吗

然后使用index从temp_lst中找到具有0值的索引，然后用它来推导k。如果在试图查找的索引之前temp_lst上有另一个0值，那么这种方法显然不起作用。我们可以很容易地创建一个可能是这种情况的输入，例如在代码表的开头添加11两次，这样整个代码表就是[11, 11, 11, 13, 8, 10, 12, 16]。你知道吗

编辑为什么不使用后续数字差异的初始方法来查找k？下面的代码在代码表上循环，并为每个位置检查普通序列是否可以从那里开始，即，如果数字等于或大于普通序列中的第一个数字，因为k被定义为非负整数。然后它在代码表和普通序列上循环下一个b - 1数字，以查看差异是否匹配。你知道吗

最坏情况下的时间复杂度是O（ab），如果这还不够好，可以利用KMP进行更快的匹配。你知道吗

with open('safein.txt') as in_file:
    a, b = (int(x) for x in in_file.readline().split())
    code = [int(in_file.readline()) for _ in range(a)]
    plain = [int(in_file.readline()) for _ in range(b)]

for i in range(a):
    k = code[i] - plain[0]
    if k < 0:
        continue

    for j in range(1, b):
        if code[i] - code[i + j] != plain[0] - plain[j]:
            break
    else:
        break # found match, break outer loop

with open('safeout.txt', 'w') as out_file:
    out_file.write('\n'.join(str(x - k) for x in code))