Caesar Cipher凯撒密码

题目如下：（注意可能不按字典序排列）

这些入门算法题处境很尴尬，大佬轻松ac，像我这种小白查了半天资料不知道怎么搞，这样一来，我这种弱鸡网上就没得嫖 ，蒟蒻玩家表示初学很心累。
主要是kmp算法，如果不懂参考这篇文章：什么是kmp算法。
先说下题意吧，给出字符A,明文w,和加密文s，在s中单词w只会出现一次（注意题目黑体字，英语不好我纳闷这题很久 ），输出位移密码即可。
当然先处理字符串，A中只包含a-z;A-Z;0-9;这些都是ascii码表中字符，凯撒密码按照一个shift值来排密码，此处不一定按字典序，比如三例D7a,有三种可能对应情况，位移0,1,2。
也就是说把w中的D7a字符换成D7a,7aD,aD7;（为什么要换w？因为我喜欢爱好 ，因为w不超过50000而text S大小500000）在s中查找w换掉任一项字符串即可，这样位移为1的时候，D7a换成7aD，只出现了一次，位移为2时，D7a换成a7D，在s中只出现一次。
怎么换呢？从A中去查对应位移后字符 ，这显然查到超时了，既然A中字符就26+26+10个，那直接建立一个62大小数组按顺序把a-z;A-Z;0-9替换即可，当然这些都是ascii表中数字，直接建立一个128大小的数组来换也不算耗空间，而且简单。
定义一个int型ascii[128]数组，比如D7a位移1位是7aD，这样‘D’会换成‘7’字符，（D的坐标加1就是7的位置）只需要在‘D’位置（字符’D’转成int型是68）换成‘7’字符大小即可。

for (int i = 0; i < la; i++) {ord1 = a[i];ord2 = a[(i + k) % la];//k是位移数，la是字符串A的长度ascii[ord1] = ord2 ;//ascii数组用来转换字符}

然后转换w字符串

for (int i = 0; i < lw; i++) {//lw是w字符串长度nw[i] =ascii[w[i]];}

这样用nw和S进行kmp查找，查找到出现大于一次就返回重新把位移k++,如果等于一次就说明这个位移k就是密码。0次说明密码不对，k++；
ac代码（这个时间复杂度还是比较高O(n2)，直接用的板子kmp返回字符串x在y中出现次数，因为太菜越改越多bug ，大佬可能做法更巧妙）

#include
#include
#include
using namespace std;
const int maxn = 1000005;
int nxt[maxn];
void getnext(char *s)
{int i = 0, j = -1, len = strlen(s);nxt[0] = -1;while (i < len){if (j == -1 || s[i] == s[j]){if (s[++i] == s[++j])    nxt[i] = nxt[j];else    nxt[i] = j;}else    j = nxt[j];}
}int kmp(char *x, char *y)
{getnext(x);int i = 0, j = 0, ans = 0, leny = strlen(y), lenx = strlen(x);while (i < leny){if (j == -1 || x[j] == y[i]){i++, j++;if (j == lenx){ans++;j = nxt[j];}}else    j = nxt[j];}return ans;/实际上不用返回次数，定义一个bool型在循环体内部判断ans>1就返回false减少查找
}int main() {int n;char a[65];int aa[65];char w[50005], t[500005];char nw[50005];int ascii[128];int ord1, ord2;cin >> n;while (n--) {cin >> a >> w >> t;int la = strlen(a);int lw = strlen(w);int lt = strlen(t);int num = 0;//num统计解的个数for (int k = 0; k < la; k++) {//k表示位移，只能是0~A的长度-1；for (int i = 0; i < la; i++) {ord1 = a[i];ord2 = a[(i + k) % la];ascii[ord1] = ord2 ;}for (int i = 0; i < lw; i++) {nw[i] =ascii[w[i]];}nw[lw] = '\0';if (kmp(nw, t)==1) {aa[num++] = k;}}if (num == 0)cout << "no solution" << endl;else if (num == 1)cout << "unique: " << aa[0] << endl;else {printf("ambiguous:");for (int i = 0; i < num; i++) {printf(" %d", aa[i]);}printf("\n");}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！