题解：P17844 串操作

zzc2025 · 2026-11-06 15:13:16 · 题解

原串可以变成很多种新串，我们不好正向求，不妨将操作倒过来。

原来的操作就变成将

• 选择一个 \texttt{1} 子串，将其替换为 \texttt{01}
• 选择一个 \texttt{0} 子串，将其替换为 \texttt{10}

可以发现操作的特征为在一个字符前面加入一个不同的字符。

记 s 为 S 后缀的极长同颜色段，因此匹配的充要条件为 s 也是 t 的后缀，且在 S 存在一个子序列使其等于 t。

考虑怎么实现这个东西，我们直接匹配后缀，然后记一个数组 nxt_{i,c} 表示在 1\sim i 中，最靠右的字符等于 c 的下标是什么。

贴个代码：

#include<bits/stdc++.h>
// #define int long long
using namespace std;
/*
#pragma region 哈基米
*/
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-')f=-1;if(c==EOF) return 0;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
inline string reads(){
    string s=" ";char c=getchar();
    while(c>'1'||c<'0') c=getchar();
    while(c>='0'&&c<='1') {s+=c;c=getchar();}
    return s;
}
const int N=2e5+5;
int n,m,p[N],nxt[N][2];string s;
signed main(){
    // freopen("1.in" ,"r",stdin );
    n=read();s=reads();m=read();
    for(int i=1;i<=n;i++) p[s[i]-'0']=i,nxt[i][0]=p[0],nxt[i][1]=p[1];
    while(m--) {
        string t=reads();const int l=t.size()-1;int i=n,j=l;
        while(i>=1&&j>=1&&s[i]==s[n]) {
            if(t[j]!=s[i]) {j=-1;break;}
            i--,j--;
        }
        if(i>=1&&s[i]==s[n]) {printf("NO\n");continue;}
        for(;i>=1&&j>=1;j--) i=nxt[i][t[j]-'0']-1;
        if(j==0&&(i!=(-1))) printf("YES\n");else printf("NO\n");
    }
    return 0;
}