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