zcmimi's blog
查看原题

点击跳转

记录每个单词的hash值

然后按照题目所说操作

#include<bits/stdc++.h>
#define il inline
#define ull unsigned long long 
using namespace std;
const int N=1e5+5;const ull B=233;
ull h[N],H[25],S[N],b[25];
int n,m;char s[25]; 
il int find(ull x){
    int l=1,r=n,mid;
    while(l<=r) (h[mid=l+r>>1]<=x)?l=mid+1:r=mid-1;
    return h[l-1]==x&&x;
}
int main(){
    ios::sync_with_stdio(0);
    b[0]=1;for(int i=1;i<=21;++i) b[i]=b[i-1]*B;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>s+1;
        for(int j=1,lg=strlen(s+1);j<=lg;++j) h[i]=h[i]*B+s[j]-96;
    }
    sort(h+1,h+n+1);
    while(m--){
        cin>>s+1;int lg=strlen(s+1),ct=0;S[lg+1]=0;
        for(int i=1;i<=lg;++i) H[i]=H[i-1]*B+s[i]-96;
        for(int i=lg;i>=1;--i) S[i]=S[i+1]+(s[i]-96)*b[lg-i];
        if(find(H[lg])){printf("-1\n");continue;}
        for(int i=0;i<lg;++i) if(s[i]^s[i+1])
        if(find(H[i]*b[lg-i-1]+S[i+2])) ++ct;
        for(int i=0;i<=lg;++i) for(int j=1;j<=26;++j) if(j!=s[i]-96)
        if(find(H[i]*b[lg-i+1]+j*b[lg-i]+S[i+1])) ++ct;
        for(int i=1;i<=lg;++i) for(int j=1;j<=26;++j)
        if(find(H[lg]+(j-s[i]+96)*b[lg-i])) ++ct;
        printf("%d\n",ct);
    }
}
LG 4407 [JSOI2009]电子字典
comment评论
Search
search