QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128731#552. 字符串匹配问题SoyTony#0 3ms11884kbC++142.9kb2023-07-21 15:17:582023-07-21 15:33:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-21 15:33:33]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:11884kb
  • [2023-07-21 15:17:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn=(1<<20)+10;
const int mod=998244353;
const int base1=19260817;
const int base2=993244853;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

inline int q_pow(int A,int B,int P){
    int res=1;
    while(B){
        if(B&1) res=1ll*res*A%P;
        A=1ll*A*A%P;
        B>>=1;
    }
    return res;
}

int rev[maxn];
int base,w[maxn];
struct Poly{
    const static int g=3;
    const static int inv_g=332748118;
    int deg;
    vector<int> f;
    int& operator[](const int& i){return f[i];}
    int operator[](const int& i)const{return f[i];}
    inline void set(int L){deg=L;f.resize(L);}
    inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
    inline void output(int L){for(int i=0;i<L;++i)printf("%d ",f[i]);printf("\n");}
    inline void NTT(int L,bool type){
        for(int i=1;i<L;++i){
            rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
            if(i<rev[i]) swap(f[i],f[rev[i]]);
        }
        for(int d=1;d<L;d<<=1){
            base=q_pow(type?g:inv_g,(mod-1)/(2*d),mod);
            w[0]=1;
            for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%mod;
            for(int i=0;i<L;i+=d<<1){
                for(int j=0;j<d;++j){
                    int x=f[i+j],y=1ll*w[j]*f[i+d+j]%mod;
                    f[i+j]=(x+y)%mod,f[i+d+j]=(x-y+mod)%mod;
                }
            }
        }
        if(!type){
            int inv_L=q_pow(L,mod-2,mod);
            for(int i=0;i<L;++i) f[i]=1ll*f[i]*inv_L%mod;
        }
    }
}F,G,H;

int n,m;
char s[maxn],t[maxn];
int pw1[27],pw2[27];
int ans1[maxn],ans2[maxn],ans[maxn];
int cnt;
int main(){
    scanf("%s",t);
    scanf("%s",s);
m=strlen(t+1),n=strlen(s+1);
    for(int i=0;i<m;++i){
        if(i<m-1-i) swap(t[i],t[m-1-i]);
    }
    int L=1;
    while(L<n+m) L<<=1;
    pw1[0]=1,pw2[0]=1;
    for(int i=1;i<26;++i) pw1[i]=1ll*pw1[i-1]*base1%mod,pw2[i]=1ll*pw2[i-1]*base2%mod;
    F.set(L),G.set(L),H.set(L);
    for(int i=0;i<n;++i) F[i]=(s[i]!='*');
    for(int i=0;i<m;++i) G[i]=(t[i]!='*');
    F.NTT(L,1),G.NTT(L,1);
    for(int i=0;i<L;++i) H[i]=1ll*F[i]*G[i]%mod;
    H.NTT(L,0);
    for(int i=1;i+m-1<=n;++i){
        ans1[i]=1ll*H[i-1+m-1]*pw1[25]%mod;
        ans2[i]=1ll*H[i-1+m-1]*pw2[25]%mod;
        ans[i]=1;
    }
    F.clear(0,L-1),G.clear(0,L-1);
    for(int i=0;i<n;++i) F[i]=(s[i]!='*')?pw2[s[i]-'a']:0;
    for(int i=0;i<m;++i) G[i]=(t[i]!='*')?pw2[25-(t[i]-'a')]:0;
    F.NTT(L,1),G.NTT(L,1);
    for(int i=0;i<L;++i) H[i]=1ll*F[i]*G[i]%mod;
    H.NTT(L,0);
    for(int i=1;i+m-1<=n;++i){
        ans[i]&=(H[i-1+m-1]==ans2[i]);
        cnt+=ans[i];
    }
    if(cnt){
        for(int i=1;i+m-1<=n;++i){
            if(ans[i]) printf("%d ",i);
        }
        printf("\n");
    }
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 20
Accepted
time: 3ms
memory: 11884kb

input:

cabacacccbacccaabacacaabcabbabcaccbcabbacbcb
aaaccabacaaabb*abaaaa*bcabacacccba*ccaabacadaabcabba*kac*b*abbacabacacccbacccaa*acacaabcabbabca***cabbacbcbcabbacbcbbccbcacbaccbacaacc***bbbabccc**bbcbaaaaaabaabaacbc*cbcca*ccbabbacb*caaabcaba*acccbacccaabcabadac*cbacccaabacacaabca**abcucc*cxbbacb*bbacacc...

output:

64 255 424 477 591 685 794 

result:

ok 7 numbers

Test #2:

score: -20
Wrong Answer
time: 3ms
memory: 11860kb

input:

caacacbabcbbbbaccbabcba
b*b*aabcaaccya**cbabcbbo**ccbabcb*b*aacacbabaca*c*abcacacaacacba*cbbbbaccba*c*caacacbabcbbbbaccbabcbaacbabcbbbb*ccbabc*abacbcbbbaaaaccaa*acbbaacacc*ac*cb*bcbb*baccbabcbaabcbaaaabccsaabacab**aac*bacbaacaacacba**bbb*ncc*abxbabbbca*cacbabc*bbbaccbabcbabbb*abaccbcccbc**bccbb***cc...

output:

57 79 147 227 339 432 644 696 743 905 928 

result:

wrong answer 1st numbers differ - expected: '79', found: '57'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%