Topcoder SRM 663 DIV 1

ABBADiv1

题意：

规定两种操作，一种是在字符串的末尾添加A，另一种是在末尾添加B然后反转字符串。现在给你一个起始串，一个终点串，然后问你是否能够通过以上两种操作，从起始串变为终点串。

题解：

将问题反过来考虑，那么问题就变为了是否能够从终点串变为起始串。令起始串为s，终点串为t。

首先考虑串t就是串s的子串，那么这个子串的前面的B的数量一定要和这个子串后面的B的数量相同，这是因为，只有相同的时候才能消掉。并且如果第一字符不是B，且匹配的位置不是在第一个，那么第一次的反转就无法成功，即s前面的那些A是消不掉的。

第二种情况就是t的反转时s的子串，做法和前面相似，只是判断条件变为了子串前面的B的数量要比后面的B的数量小1。

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;class ABBADiv1 {
public:string canObtain(string initial, string target) {string s = initial, t = target;int pos = -1;while (true) {pos = t.find(s, pos + 1);if (pos == t.npos)break;int B0 = 0, B1 = 0;for (int i = 0; i < pos; i++)if (t[i] == 'B')B0++;for (int i = pos + s.length(); i < t.length(); i++)if (t[i] == 'B')B1++;if (B0 == B1) {if (pos == 0)return "Possible";else if (t[0] == 'B')return "Possible";}}reverse(s.begin(), s.end());pos = -1;while (true) {pos = t.find(s, pos + 1);if (pos == t.npos)break;int B0 = 0, B1 = 0;for (int i = 0; i < pos; i++)if (t[i] == 'B')B0++;for (int i = pos + s.length(); i < t.length(); i++)if (t[i] == 'B')B1++;if (B0 == B1 + 1 && t[0] == 'B')return "Possible";}return "Impossible";}
};