「ch57」凯撒密码

2015年4月9日3,8830

[Description]

Gemini最近喜欢上了历史,他了解到历史上有一种神奇的加密方法叫做凯撒密码。

凯撒密码非常的简单,就是把每个字母向后移动m位(z的后一位是a)。例如,当m = 1,abcd加密后就是bcde,当m = 5,xyz加密后会变成cde。

Gemini对学会一种加密方法表示非常兴奋,于是,他构造了大量长度为5的纯英文小写密文(为什么是5?我也不知道)。然后……,然后他把哪个明文对应哪个密文搞混了。(-_-|||)

幸运的是,经过分析,还是可以找出明密文的对应关系的,比如“dtfeg”,“tiyoj”,“eugfh”,“vkaql”四个串,明显“dtfeg”,“eugfh”相互对应(m = 1),“tiyoj”,“vkaql”相互对应(m = 2)。

然而,看到海量的字符串,Gemini失去了手动匹配的信心,于是他机智地拿出了Raspberry Pi,开始写程序。

[Input]

第一行,一个整数N,表示有N段明文,N段密文。

第二行,N个长度为5的字符串,表示N段密文。

第三行,N个长度为5的字符串,表示N段明文。

[Output]

N行,每行两个整数ai,mi。ai表示第i段明文对应的密文编号(从1开始),mi表示从第i段明文加密得到第i段密文所用的密钥m。

[Sample]

Sample Input    Sample Output
2

eugfh vkaql

dtfeg tiyoj

   1 1

2 2

[Hint]

2 ≤ N ≤ 300 000。

保证有且只有一组解。

m的取值范围为[0,25]

题解

搬运:把相邻两个字符之间的差值(注意是同余意义上的差值)看做一个4位26进制数进行
hash。那么具有相同hash的字符串一定一一对应。

 

avatar
  Subscribe  
提醒