G.String Transformation
题目描述
Bobo has a string S = s1 s2...sn consists of letter a , b and c . He can transform the string by inserting or deleting substrings aa , bb and abab .
Formally, A = u ◦ w ◦ v (“ ◦ ” denotes string concatenation) can be transformed into A 0 = u ◦ v and vice versa where u , v are (possibly empty) strings and w ∈ { aa , bb , abab } .
Given the target string T = t1 t2 . . . tm , determine if Bobo can transform the string S into T .
Formally, A = u ◦ w ◦ v (“ ◦ ” denotes string concatenation) can be transformed into A 0 = u ◦ v and vice versa where u , v are (possibly empty) strings and w ∈ { aa , bb , abab } .
Given the target string T = t1 t2 . . . tm , determine if Bobo can transform the string S into T .
输入
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains a string s1 s2 ...sn . The second line contains a string t1 t2 . . . tm .
The first line of each test case contains a string s1 s2 ...sn . The second line contains a string t1 t2 . . . tm .
输出
For each test case, print Yes if Bobo can. Print No otherwise.
• 1 ≤ n, m ≤ 10 4
• s1 , s2 ,..., sn , t1 , t2 , . . . , tm ∈ { a , b , c }
• The sum of n and m does not exceed 250,000.
• 1 ≤ n, m ≤ 10 4
• s1 , s2 ,..., sn , t1 , t2 , . . . , tm ∈ { a , b , c }
• The sum of n and m does not exceed 250,000.
样例输入
ab
ba
ac
ca
a
ab
样例输出
Yes
No
No
提示
For the first sample, Bobo can transform as ab => aababb => babb => ba .
题意
给定两个字符串S和T，只包含a,b,c三种字母，对S串通过插入和删除（只能是'aa','bb','abab'），问S串能否变成T串。
思路
可以发现字母c起着分隔的作用，对S和T分别用数组保存每段a和b的个数，再对每段分别判断：因为'aa','bb'可以直接删除，所以两个串每段剩下来的一定是a，b交叉呈现的，通过样例一可以知道'ab','ba'可以相互转变,再将'abab'全部从两个串每段中删掉，发现剩下来的就只有'a','b','ab','ba','aba','bab',还有空这七种字符串。不难判断只有当S和T的每段删下来对应的字符串相等或不等为'ab','ba'时可以判Yes，其余都是判定为No。
到这就发现对每段都是删除'aa','bb','abab',发现删的都是a和b的偶数个，而要判断的就只有最后剩下来的七种情况，
所以有
a b
a 1 0
b 0 1
ab(ba) 1 1
aba 2 1
bab 1 2
空 0 0
所以只要判断每段a和b的奇偶性是否相同就可以了。
代码
#include <bits/stdc++.h>
#define me(a) memset(a,0,sizeof(a));
typedef long long ll;
const int N=1e4+10;
using namespace std;
char a[N], b[N];
int la[N], lb[N], ra[N], rb[N];
int main(){
while(~scanf("%s %s", a, b)){
me(la);me(lb);me(ra);me(rb);
int sa = strlen(a);
int sb = strlen(b);
int k = 0;
for(int i=0; i<sa; i++){
if(a[i] != 'c'){
if(a[i] == 'a') la[k]++;
else lb[k]++;
}
else k++;
}
int j = 0;
for(int i=0; i<sb; i++){
if(b[i] != 'c'){
if(b[i] == 'a') ra[j]++;
else rb[j]++;
}
else j++;
}
if(k != j) printf("No\n");
else {
int g = 1;
for(int i=0; i<=k; i++){
if((la[i]%2 != ra[i]%2) || (lb[i]%2 != rb[i]%2))
g = 0;
}
if(g) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}