爱名网22自助网站建设,百度竞价推广开户,企业邮箱服务,网络软件设计題目#xff1a;給你一個字符串#xff0c;在後面拼接一部分使得它變成回文串#xff0c;使得串最短。輸出這個回文串。分析#xff1a;KMP#xff0c;dp。這裡利用KMP算法將串和它的轉置匹配#xff0c;看結束時匹配的長度就可以。 因為串比较長。使用KMP比较合適#… 題目給你一個字符串在後面拼接一部分使得它變成回文串使得串最短。輸出這個回文串。 分析KMPdp。這裡利用KMP算法將串和它的轉置匹配看結束時匹配的長度就可以。 因為串比较長。使用KMP比较合適KMP原理請参照AC自動機總結。 說明╮(╯▽╰)╭。 #include string.h
#include stdio.h
#include stdlib.hchar 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;
}转载于:https://www.cnblogs.com/claireyuancy/p/7091734.html
