UVa 11475 : Extend to Palindromes
問題リンク : http://uva.onlinejudge.org/external/114/11475.html
問題概要:
大文字か小文字のアルファベットからなる空ではない文字列が与えられる
この文字列に0以上のアルファベットを追加して長さが最小の回文を作れ
解法:
与えられた文字列の後ろからみて最も長い回文をみつけ、それ以外の場所を反転してくっつけた
例えば、
nadexnadan という文字列が与えられたとき、一番後ろからみて最もながい回文は nadan である
なので、もとの文字列のそれ以外の文字列を反転してくっつける
nadexnadan -> nadex -> xedan
nadexnadan + xedan = nadexnadanxedan
KMPを利用した
コード:
#include<iostream> #include<cmath> #include<cstdio> #include<cassert> #include<cctype> #include<climits> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define IINF (INT_MAX) #define MAX 1000010 using namespace std; string line; int b[MAX]; void kmpPreprocess(const string& P) { int i=0,j = -1; b[0] = -1; int m = P.size(); while(i < m) { while(j >= 0 && P[i] != P[j])j = b[j]; i++; j++; b[i] = j; } } int kmpSearch(const string& T,const string& P) { int i=0,j=0; int n = T.size(); int m = P.size(); while(i < n) { while(j >= 0 && T[i] != P[j])j = b[j]; i++, j++; } return j; } int main() { string P; while(getline(cin,P)) { assert(P.size()+1 < MAX); string revP = string(P.rbegin(),P.rend()); kmpPreprocess(revP); int len = kmpSearch(P,revP); cout << P << revP.substr(len,revP.size()-len) << endl; } return 0; }