土下座しながら探索中

主に競技プログラミング

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