質問の概要📌

質問リンク📢

https://www.acmicpc.net/problem/12919

問題を解く📝

初めて見た時に思いついたSがTを作る方法はいろいろあり、近づきにくいです.そこで,逆TでSを作成する方法を選択する.
筆者はC++が提供する文字列関数と再帰的完全検索によってコミュニケーションを得た.
Tから、1文字目がAとBの場合は別々に条件処理を行い、完全探索を行い、TがSでない場合は0を出力する.

コード#コード#

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

string S, T;
bool flag = false;
string Recursion(string str)
{
	if (str.size() == S.size() || flag) // S와 길이가 같아졌거나 이미 그 문자열을 만들 수 있다면
	{
		if (str == S) 
			flag = true;
		return str;
	}
	if (str.size() > 0)
	{
		if (str[0] == 'A') // 첫 번째 문자가 A인 경우
		{
			if (str.back() == 'A')
			{
				str.pop_back();
				Recursion(str);
				str.push_back('A');
			}
		}
		else // 첫 번째 문자가 B인 경우
		{
			string tmp = str;
			reverse(tmp.begin(), tmp.end());
			str = tmp;

			str.pop_back();
			Recursion(str);

			reverse(tmp.begin(), tmp.end());
			str = tmp;
			if (str.back() == 'A') // 마지막 문자가 A인 경우
			{				
				str.pop_back();
				Recursion(str);
				str.push_back('A');
			}			
		}
	}
	return str;
}
int main()
{
	cin >> S >> T;
	Recursion(T);
	cout << flag;
	return 0;
}