[ABC287D] Match or Not

_JF_ · 2023-02-05 14:19:53 · 题解

[ABC287D] Match or Not

有意思的简单题.

我们不妨把第一个字符串设为 a 串，第二个设为 b 串。

显然，如果一个 a 串的一个字母有用去组成新的串和 b串进行比较，那么只要用到这个字母，他所对应的 b 串的字母就是一样的，不会改变。

很自然想到前缀和。

如果当前 a 串这个字母和 b 串对应字母匹配，那就标记为 0，不匹配就标记为 1。

由于 a 串需要有两个部分去组成新的字符串比对，所以考虑预处理两个前缀和数组，一个是从后往前，一个是从前往后。

如果当前询问长度为 i 的串，那就是从前往后的长度是 i。从后往前的长度就是 size(b)-i。

查询这两部分的和是不是 0 判断就好。

    #include<bits/stdc++.h>
    using namespace std;
    const int N =1e6+10;
    char s[N],t[N];
    int s1[N],s2[N];
    int main()
    {
        scanf("%s",s+1);
        scanf("%s",t+1);
        int n=strlen(s+1);
        int n1=strlen(t+1);
        for(int i=n-n1+1,j=1;i<=n;i++,j++)
        {
            if(s[i]==t[j]||s[i]=='?'||t[j]=='?')
                s1[j]=0;
            else
                s1[j]=1;
        }   
        for(int i=1;i<=n1;i++)
        {
            if(s[i]==t[i]||s[i]=='?'||t[i]=='?')
                s2[i]=0;
            else
                s2[i]=1;
        }
        for(int i=1;i<=n1;i++)
            s1[i]+=s1[i-1],s2[i]+=s2[i-1];
        for(int i=0;i<=n1;i++)
        {
            if(s1[n1]-s1[i]+s2[i]==0)//
                 cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    /*
    a?c
    b?
    */