Morris' Blog 我在摸索我存在的意、生命的意、涵及值。 有真正神手般的害，套用模式是大部分的情。 那害的我存在的意何，托出神的存在？ 有候不能怪人不我，我已始省思， 什我有人的原因，而是全要靠人。 有候我我不同，那是因我做不到很多人能到的事情。 我不到、玩不起、得不明、理解得不多， 我缺少的文能力，就是一切一切能的判定。 此，我不得能做些人有助的事情。 我知道我自己是不服的性格，但在我不得不。 我有能力，因此我必。 我到底世界作什？充不定性， 而我是法出拔萃，想一般人似乎也回不了了。 越大的挑需要越力的支持，而我的支持是什？ 最近人，但都是失的局，人能接受， 不需要言，不需要通，一切所想都表不出。

49的鼓 6站台

Problem C: Caesar cipher

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet (wrapping around in the end). For example, given an alphabet of capital letters in usual order, with a shift of 3, A would be replaced by D, B would become E, and so on, with Z being replaced by C. The method is named after Julius C Caesar, who used it in his private correspondence.

We are given an alphabet A, a string S which is encrypted using a shift cipher and a plaintext word W.
Find the possible values of shifts (in the range [0, |A|-1]) used in encryption if we know that the unencrypted text contains exactly one occurrence of the word W.

Input Format

Input starts with an integer N on a line, the number of test cases. Each cases contains three strings on separate lines, alphabet A, plaintext word W and encrypted text S. Alphabet A will contain only letters and digits ([A-Z][a-z][0-9]) and its symbol order is not necessarily lexicographical (see the third sample case). A will not contain duplicate symbols. The constraints are as given: 3<=|A|<=62, 1<=|W|<=50,000, 3<=|S|<=500,000.

Output Format

For each test case print one line of output. If there are no shifts that would satisfy the condition of W being a part of the unencrypted S, print "no solution". If there is exactly one shift that could have been used, print "unique: #" where # is the shift value. It there are more than one possible shifts print "ambiguous: " followed by the sorted list of shift values.
For clarification, see the sample output.

Sample Input

4 ABC ABC ABCBBBABC ABC ABC ABCBCAABC D7a D7a D7aaD77aDD7a ABC ABC ABC 

Sample Output

no solution unique: 1 ambiguous: 1 2 unique: 0

#include <stdio.h>
#include <string.h>
char A[1024], W[500005], S[500005];
int kmpTable[500005];
void KMPtable(char *P, int len) {
 int i, j;
 kmpTable[0] = -1, i = 1, j = -1;
 while(i < len) {
 while(j >= 0 && P[j+1] != P[i])
 j = kmpTable[j];
 if(P[j+1] == P[i])
 j++;
 kmpTable[i++] = j;
 }
}
int KMPMatching(char T[], char P[], int tlen, int plen) {
 int i, j;
 int matchCnt = 0;
 for(i = 0, j = -1; i < tlen; i++) {
 while(j >= 0 && P[j+1] != T[i])
 j = kmpTable[j];
 if(P[j+1] == T[i]) j++;
 if(j == plen-1) {
 matchCnt++;
 j = kmpTable[j];
 if(matchCnt >= 2)
 return matchCnt;
 }
 }
 return matchCnt;
}
char E[500005];
int main() {
 int testcase;
 int i, j, k;
 scanf("%d", &testcase);
 while(getchar() != '\n');
 while(testcase--) {
 gets(A);
 gets(W);
 gets(S);
 int Alen = strlen(A);
 int Wlen = strlen(W);
 int Slen =strlen(S);
 int CHAR[1024] = {};
 for(i = 0; A[i]; i++)
 CHAR[A[i]] = i;
 int ret[1024], ridx = 0;
 for(i = 0; i < Alen; i++) {
 for(j = 0; j < Wlen; j++)
 E[j] = A[(CHAR[W[j]]+i)%Alen];
 E[Wlen] = '\0';
 KMPtable(E, Wlen);
 int cnt = KMPMatching(S, E, Slen, Wlen);
 if(cnt == 1)
 ret[ridx++] = i;
 }
 if(ridx == 0)
 puts("no solution");
 else if(ridx == 1)
 printf("unique: %d\n", ret[0]);
 else {
 printf("ambiguous:");
 for(i = 0; i < ridx; i++)
 printf(" %d", ret[i]);
 puts("");
 }
 }
 return 0;
}

您可能以下文章有趣

[UVA][走] 372 - WhatFix Notation

[UVA][二分婪] 1199 - Elevator Stopping Plan

[UVA] 886 - Named Extension Dialing

[UVA][影像四分] 874 - 2D Representations