http://acm.hdu.edu.cn/showproblem.php?pid=4300
题意：
给出两个字符串，第一个字符串是加密表，是用来将明文转化成密文的。
第二个字符串是密文+明文，而且密文是完整的，但是明文不一定完整，现在要根据密文和加密表把所有明文表示出来，要求整个字符串长度最小。
思路：
看懂题意之后就比较好做了，原串的明文是后缀，现将原串根据加密表全部转化成明文，那么此时前缀就是明文，如果药整个字符串长度最小，那么确定的明文当然是越多越好了，计算一下最长公共前缀。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<map> 5 using namespace std; 6 const int maxn = 1000000+5; 7 8 char s1[maxn],s2[maxn], p[30]; 9 int nxt[maxn],extend[maxn]; 10 11 map<char,char> mp; 12 13 14 void preekmp(char x[], int m) 15 { 16 nxt[0] = m; 17 int j = 0; 18 while(j+1 <m && x[j] == x[j+1]) j++; 19 nxt[1] = j; 20 int k = 1; 21 for(int i=2;i<m;i++) 22 { 23 int p = nxt[k]+k-1; 24 int L = nxt[i-k]; 25 if(i+L<p+1) nxt[i] = L; 26 else 27 { 28 j = max(0,p-i+1); 29 while(i+j<m && x[i+j]==x[j]) j++; 30 nxt[i] = j; 31 k = i; 32 } 33 } 34 return; 35 } 36 37 void ekmp(char x[],int m,char y[],int n) 38 { 39 preekmp(x,m); 40 int j = 0; 41 while(j<n && j<m && x[j] == y[j]) j++; 42 extend[0] = j; 43 int k = 0; 44 for(int i=1;i<n;i++) 45 { 46 int p = extend[k]+k-1; 47 int L = nxt[i-k]; 48 if(i+L<p+1) extend[i]=L; 49 else 50 { 51 j = max(0,p-i+1); 52 while(i+j<n && j<m && y[i+j]==x[j]) j++; 53 extend[i] = j; 54 k = i; 55 } 56 } 57 return; 58 } 59 60 int main() 61 { 62 //freopen("in.txt","r",stdin); 63 int T; 64 scanf("%d",&T); 65 while(T--) 66 { 67 mp.clear(); 68 scanf("%s%s",p,s1); 69 int n = strlen(s1); 70 for(int i=0;p[i];i++) mp[p[i]]='a'+i; 71 memset(s2,0,sizeof(s2)); 72 for(int i=0;i<n;i++) s2[i] = mp[s1[i]]; 73 ekmp(s2,n,s1,n); 74 int ans = n; 75 for(int i=0;i<n;i++) 76 { 77 if(i+extend[i]>=n && i>=extend[i]) 78 { 79 ans = i; 80 break; 81 } 82 } 83 for(int i=0;i<ans;i++) printf("%c",s1[i]); 84 for(int i=0;i<ans;i++) printf("%c",mp[s1[i]]); 85 printf(" "); 86 } 87 return 0; 88 }