题目描述
由相邻位置的字符确定目标字符的加密方式。对给出的密文解密。
思路
破解密码的策略
1.利用边界,密文的第1个字符是原文的第2个字符。
有了原文的第2个字符,结合密文的第3个字符即可得到原文的第4个字符。
…
可以求得原文的所有偶数位。
2.反向重复上述操作。
(1) 若字符串长度为偶数,则可以求得原文的奇数位,从而结合偶数位组成一个可行的原文。
事实上,因为编码方式是两个字符相加对26取余数,所以每次得到的原文字符是唯一的。
(2) 若字符串长度为奇数,则将求得另一组原文的偶数位,两次的答案很可能冲突。
另外,没有被求解的原文奇数位,使用相同的方法,对任意输入都将产生合理的解,即一定有歧义的解。
求解原文
1.当字符串长度为奇数时,直接输出’AMBIGUOUS’。
2.当字符串长度为偶数时,正反两轮迭代生成原文的各个字符。
时间复杂度
长度N为偶数时,生成N次字符,每次都是做简单计算即可,复杂度O(N)。
python3 代码
T = int(input())
for C in range(T):
code = input()
if (len(code)%2):
print("Case #%d: %s"%(C+1, 'AMBIGUOUS'))
else:
# 字符串不可修改,用list表示。
origin = [0] * len(code)
origin[1]=code[0]
for i in range(1, int(len(origin)/2)):
origin[2*i+1] = chr((ord(code[2*i])-ord(origin[2*i-1]))%26 + 65)
origin[-2]=code[-1]
for i in range(1, int(len(origin)/2)):
origin[-2*(i+1)] = chr((ord(code[-(2*i+1)])-ord(origin[-2*i]))%26 + 65)
print("Case #%d: %s"%(C+1, ''.join(origin)))