HDOJ 4300 Clairewd's message(扩展KMP)
超级传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4300
本题题意是给你一个字符对应表，再给一个密文和明文相连接的串(明文后缀可能缺失)，求补全后的串。
比如样例：
#include <cstdio>#include <cstring>using namespace std;int P[100010];char table[26], rev_table[26];char B[100010];int ex_preprocess(char* B, int* P, int m = -1){ int a = 0, p, L; if (m == -1) m = strlen(B); P[0] = m; while (a < m - 1 && B[a] == table[B[a + 1] - 'a']) a++; P[1] = a; a = 1; for (int k = 2; k < m; k++) { p = a + P[a] - 1; L = P[k - a]; if ((k - 1) + L >= p) { int j = (p - k + 1) > 0 ? (p - k + 1) : 0; while (k + j < m && table[B[k + j] - 'a'] == B[j]) j++; P[k] = j; a = k; } else P[k] = L; if (k > ((m - 1) >> 1) && k + P[k] == m) return k; } return m;}void make_rev_table(char table[26], char rev_table[26]){ for (int i = 0; i < 26; i++) rev_table[table[i] - 'a'] = 'a' + i;}int main(){ int t; scanf("%d", &t); while (t--) { scanf("%s%s", table, B); make_rev_table(table, rev_table); int m = strlen(B); int index = ex_preprocess(B, P, m); for (int i = 0; i < index; i++) printf("%c", B[i]); for (int i = 0; i < index; i++) printf("%c", rev_table[B[i] - 'a']); printf("\n"); } return 0;}