出题人题解 | #括号串#

串是 串的一种合法补全的要求是：

1. 串的括号是匹配的
2. 串是 串的子序列

对于条件1，我们只需要用栈来记录括号是否匹配即可，对于条件 2 ，我们可以使用双指针来判断子序列。
时间复杂度

赛后出题人感想：应该还是送分到位了
联合出题人：长郡中学 Werner_yin

//https://www.cnblogs.com/werner-yin/
#include <bits/stdc++.h>

#define WA puts("Wrong Answer")
#define AC puts("Accepted")

using namespace std;

const int MAXN = 5e5+10;

int T,n,m,top = 0;
char s[MAXN],t[MAXN<<1],stk[MAXN<<1];

bool ismatch(char *x,int l){
    top = 0;
    for(int i = 0;i < l;i++)
        if(x[i] == '(' || x[i] == '[') stk[++top] = x[i];
        else if(x[i] == ']') {if(stk[top] == '[') top--;else return 0;}
        else {if(stk[top] == '(') top--;else return 0;}
    if(top) return 0; return 1;
}

int main (){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        scanf("%s",s);scanf("%s",t);
        if(!ismatch(t,m)) {WA;continue;}
        int i,j;
        for(i = 0,j = 0;i < m;i++){
            if(s[j] == t[i]) j++;
            if(j == n) {AC;break;}
        }
        if(j != n) WA;
    }
    return 0;
}