HDU 5414 CRB and String 思维好题

HDU 5414 CRB and String 思维好题

Problem Description
CRB has two strings s and t.
In each step, CRB can select arbitrary character c of s and insert any character d (d ≠ c) just after it.
CRB wants to convert s to t. But is it possible?

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case there are two strings s and t, one per line.
1 ≤ T ≤ 105
1 ≤ |s| ≤ |t| ≤ 105
All strings consist only of lowercase English letters.
The size of each input file will be less than 5MB.

Output
For each test case, output “Yes” if CRB can convert s to t, otherwise output “No”.

Sample Input

4
a
b
cat
cats
do
do
apple
aapple

Sample Output

No
Yes
Yes
No

题意：本题要求判断字符串s能否通过添加若干个字符得到字符串t。

解法：思维好题，像窝这种弱鸡真心想不到啊，首先，可以知道，s必须是t的一个子串（注意：不是连续子串）。第二，由于插入的新字符和它前面的字符c不同，因此如果t中有cnt个连续的c，那么在s中也必须有cnt个连续的c。因此，只要能够满足这2个条件，就一定可以成功实现转化。然后手推了很多样例发现确实是这样妙啊233。

#include <bits/stdc++.h>
using namespace std;
const int maxn  = 100010;
char s1[maxn], s2[maxn];
bool check(char *s1, char *s2)
{int n = strlen(s1);int m = strlen(s2);int i,j;for(j=1; j<m; j++) if(s2[j]!=s2[0]) break;for(i=0; i<j; i++) if(s1[i]!=s2[i]) return false;while(i<n){for(;j<m;j++){if(s2[j]==s1[i]){break;}}if(j == m) return false;i++,j++;}return true;
}
int main()
{int T;scanf("%d", &T);while(T--){scanf("%s", s1);scanf("%s", s2);if(check(s1, s2)){puts("Yes");}else{puts("No");}}return 0;
}