• Sources：K- LR String
• Abstract：給定僅由L與R構成的原字符串$S(1\le |S|\le 5\times 10^5)$，其中L可刪除其左側字符，R可刪除其右側字符。給出$q(1\le q\le 5\times 10^5)$組詢問，每次詢問包含一個字符串$T(1\le |T_i|\le |S|)$，判斷$T$是否經由$S$修改得到。($\sum (|S|+q+|T_i|)\le 10^6$)
• Keyword：字符串(簽到題)
• Solution：注意到$S$中，當L出現在開頭或R出現在末尾時，其將永遠無法刪除，因此當s.front()=='L'&&s.front()!=t.front()或s.back()=='R'&&s.back()!=t.back()可直接判定無解。由于$T$一定為$S$刪除某些字符得到，因此問題轉換為判定$T$是否為$S$的子序列。注意到數據范圍非常大，需設計$O(n)$的算法判斷子序列。
• Code：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#define endl "\n"
const int INF=__INT_MAX__;
void solve(){
    string s;cin>>s;
    vector<int>nxt_l(s.size(),INF),nxt_r(s.size(),INF);//S中每個字符的下個L/R位置表
    int l=INF,r=INF;
    for(int i=s.size()-1;i>=0;i--){//倒序遍歷S進行預處理
        nxt_l[i]=l,nxt_r[i]=r;
        if(s[i]=='L') l=i;
        else r=i;
    }
    int q;cin>>q;
    while(q--){
        string t;cin>>t;
        bool ok=1;
        if ((s[0]=='L'&&s[0]!=t[0])||(s[s.size()-1]=='R'&&t[t.size()-1]!=s[s.size()-1])) {//2個特例
            cout<<"NO"<<'\n';
            continue;
        }
        int idx=(t[0]=='L')?l:r;//預處理后l/r即為S中首個L/R的位置
        if (idx>=s.size()) {
            cout<<"NO"<<'\n';
            continue;
        }
        for (int i=1;i<t.size();i++) {
            idx=(t[i]=='L')?nxt_l[idx]:nxt_r[idx];
            if (idx>=s.size()) {
                ok=0;
                break;
            }
        }
        if(ok) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}