CodeFestival 2017 qualC

C - Inserting 'x' (400)

C - Inserting 'x'

概要

英小文字からなる文字列について、英小文字を好きなだけ挿入してを回文にできるとき、挿入数の最小値を求めよ。
どれだけ挿入しても回文にできないときはを出力せよ

方針

からを取り除いた文字列をとする。
が回文でなければ、どれだけを追加しても回文にならないのでを出力する。
が回文がであれば、を適切に追加すると回文にできる。
追加方法は、を前と後ろから見ていき、一致しなかった場合は片方がでないため、そこにを挿入する。

解答

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin >> s;

	int n = s.size();
	vector<char> wox;
	rep(i, n){
		if(s[i] != 'x') wox.push_back(s[i]);
	}

	bool isPalindrome = true;
	int m = wox.size();
	for(int i = 0; i < m-1-i;i++){
		if(wox[i] != wox[m-1-i]){
			isPalindrome = false;
			break;
		}
	}

	if(!isPalindrome){
		cout << -1 << endl;
		return 0;
	}

	int ans = 0;
	int l = 0;
	int r = n-1;
	while(l < r){
		if(s[l] == 'x' && s[r] != 'x'){
			ans++;
			l++;
		}else if(s[l] != 'x' && s[r] == 'x'){
			ans++;
			r--;
		}else{
			l++;
			r--;
		}
	}

	cout << ans << endl;
}