Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <stack>
- #include <tuple>
- using namespace std;
- bool ans_sec(int left, int right, string & s, char ind){
- stack<pair<int, char>> st;
- int n = s.size();
- int l = 0;
- for (int i = left + 1; i <= right + 1; i++){
- if (s[i] != s[i - 1]){
- pair<int, char> cur = {i - l, s[i - 1]};
- l = i;
- if (cur.second != ind) {
- if (st.size() > 0 && st.top().first > cur.first) {
- st.top().first += cur.first;
- } else {
- st.push(cur);
- continue;
- }
- if (st.size() > 0) cur = st.top();
- st.pop();
- }
- while (st.size() > 0 && (st.top().second == cur.second || st.top().first < cur.first)) {
- cur.first += st.top().first;
- st.pop();
- }
- st.push(cur);
- }
- }
- if (st.size() > 1 || st.top().second != ind) return false;
- else return true;
- }
- bool sol(string & s, string & t){
- int l = 0;
- int n = (int)t.size();
- for (int i = 1; i < n; i++){
- if (t[i] != t[i - 1]){
- if (s[i] == s[i - 1]) return false;
- if (!ans_sec(l, i - 1, s, t[i - 1])) return false;
- l = i;
- }
- }
- if (!ans_sec(l, n - 1, s, t[n - 1])) return false;
- return true;
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int q;
- cin >> q;
- for (int i = 1; i <= q; i++){
- string s, t;
- cin >> s >> t;
- s += "#";
- if (sol(s, t)) cout << "Yes\n";
- else cout << "No\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement