yukicoder - No.588

No.588　空白と回文

問題ページ

ひっくり返したものを少しずつずらしていって，一致する文字の最大数を調べる．
一致しない文字は削除したことにすればいい．

      abcaba
 abacba

      abcaba
  abacba

      abcaba
   abacba

      abcaba
    abacba

      abcaba
     abacba

      abcaba
      abacba

      abcaba
       abacba

      abcaba
        abacba

      abcaba
         abacba

      abcaba
          abacba

      abcaba
           abacba

たとえば

      abcaba
    abacba

であれば，共通部分以外を削除して

      a  a
      a  a

という線対称な文字列ができる．

ずらす時に生じる両端の空白について，元の文字列と反転した文字列で適当に異なる文字を埋めておけば，空白同士等しいと判定することはなくなる．

O(|S|²) なので充分間に合う．

#include "bits/stdc++.h"
using namespace std;

int main()
{
    string S;
    cin >> S;

    int N = S.size();

    string T = S;
    reverse(T.begin(), T.end());

    S = string(N, '.') + S + string(N, '.');

    int ans = 0;
    for (int i = 1; i < 2 * N; i++) {
        T = '@' + T;
        int cnt = 0;
        for (int j = 0; j < T.size(); j++) {
            if (S[j] == T[j]) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;

    return 0;
}