佛山精品网站建设,php和html5做网站,代码运行框wordpress,公司网站建设推荐乐云seo題目#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
