hdu 4300 Clairewd’s message (kmp)
吐槽：题意难懂的一逼，关键的地方根本没有说清好么。。。竟然还是多校题。。。。出题人英语是体育老师教的吧。。？本来挺傻逼一道题。。被这完全没有说清楚的题意搞得很不爽。。。
题意：给一个26个字母一一对应的密码表。
然后给出一个字符串，先是密文再是明文，明文可能不全。问最小的可能的密文+明文串是什么。。
思路：
把字符串按照密码表转化得到一个新的字符串，然后跑kmp得到原字符串a的后缀等于转化后的字符串b的前缀的最长长度的字符串。（需要注意的是,kmp匹配的时候，由于密文长度一定是大于等于明文的，并且如果字符串a和字符串b相等，匹配全部是没有意义的，所以我们从中间位置开始匹配，更具体的说，是从第一个后面的字符串的长度大于等于前面的字符串的长度的位置开始匹配）
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月12日 星期五 13时55分42秒
4File Name :code/hdu/4300.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <deque>
20#include <ctime>
21#define fst first
22#define sec second
23#define lson l,m,rt<<1
24#define rson m+1,r,rt<<1|1
25#define ms(a,x) memset(a,x,sizeof(a))
26typedef long long LL;
27#define pi pair < int ,int >
28#define MP make_pair
29
30using namespace std;
31const double eps = 1E-8;
32const int dx4[4]={1,0,0,-1};
33const int dy4[4]={0,-1,1,0};
34const int inf = 0x3f3f3f3f;
35const int N=1E5+7;
36char a[N],b[N];
37map<char,char>mp;
38char table[30];
39int nxt[N];
40void getnxt( char *s)
41{
42 int n = strlen(s);
43 int i = 0 ;
44 int j = -1;
45 nxt[0] = -1;
46 while (i<n)
47 if (j==-1||s[i]==s[j]) nxt[++i] = ++ j;
48 else j = nxt[j];
49}
50int kmp(char *a,char *b)
51{
52 int n = strlen(a);
53 getnxt(b);
54 int i = 0;
55 int j = 0;
56 if (n%2==0) i = n/2; //明文可能残缺，因此密文长度大于等于明文，i要从一半往后开始，不然的话会匹配到自身
57 else i = n/2+1;
58 while (i<n)
59 {
60 if (j==-1||a[i]==b[j]) i++,j++;
61 else j = nxt[j];
62 }
63 if (i==n) return j;
64 return 0;
65}
66int main()
67{
68 #ifndef ONLINE_JUDGE
69 freopen("code/in.txt","r",stdin);
70 #endif
71 int T;
72 cin>>T;
73
74 while (T--)
75 {
76 mp.clear();
77 scanf("%s",table);
78 for ( int i = 0 ; i < 26 ; i++) mp[table[i]]=char(i+97);
79 scanf("%s",a);
80 int len = strlen(a);
81 for ( int i = 0 ; i < len ; i++)
82 b[i] = mp[a[i]];
83 int k = kmp(a,b);
84 // cout<<"k:"<<k<<endl;
85 for ( int i = 0 ; i < len ; i++)
86 printf("%c",a[i]);
87 for ( int i = k ; i < len-k ; i++)
88 printf("%c",mp[a[i]]);
89 printf("\n");
90 }
91
92 #ifndef ONLINE_JUDGE
93 fclose(stdin);
94 #endif
95 return 0;
96}