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

分析：KMP，dp。這裡利用KMP算法將串和它的轉(zhuǎn)置匹配，看結(jié)束時(shí)匹配的長(zhǎng)度就可以。

? ? ? ? ? ? 因?yàn)榇容^長(zhǎng)。使用KMP比較合適，KMP原理請(qǐng)參照AC自動(dòng)機(jī)總結(jié)。

說(shuō)明：╮(╯▽╰)╭。

#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; }

轉(zhuǎn)載于:https://www.cnblogs.com/claireyuancy/p/7091734.html

總結(jié)

以上是生活随笔為你收集整理的UVa 11475 - Extend to Palindrome的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。