UVa 11475 - Extend to Palindrome

題目：給你一個字符串，在後面拼接一部分使得它變成回文串，使得串最短。輸出這個回文串。

分析：KMP，dp。這裡利用KMP算法將串和它的轉置匹配，看結束時匹配的長度就可以。

? ? ? ? ? ? 因為串比較長。使用KMP比較合適，KMP原理請參照AC自動機總結。

說明：╮(╯▽╰)╭。

#include <string.h>
#include <stdio.h>
#include <stdlib.h>char strA[100001];
char strB[100001];
int  next[100001];void getnext(char T[])  
{  next[0] = -1;int i = 0, j = -1;  while (T[i]) {  if (j == -1 || T[i] == T[j]) {++ i; ++ j;if (T[i] != T[j])next[i] = j;else next[i] = next[j];  }else j = next[j];  }
}  int KMP(char S[], char T[])
{int i = 0, j = 0;while (S[i]) {if (j == -1 || S[i] == T[j]) {i ++; j ++;}else j = next[j];}return j;
}int main()
{while (~scanf("%s",strA)) {int len = strlen(strA);for (int i = 0; i < len; ++ i)strB[i] = strA[len-1-i];strB[len] = 0;getnext(strB);printf("%s%s\n",strA,&strB[KMP(strA, strB)]);}return 0;
}