0分求助(字符串Hash+悬关)
  • 板块P3763 [TJOI2017] DNA
  • 楼主Zikl
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/10 01:07
  • 上次更新2023/11/10 01:25:44
查看原帖
0分求助(字符串Hash+悬关)
300166
Zikl楼主2023/11/10 01:07

马蜂良好:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>
#define ULL unsigned long long
using namespace std;
const int b=233,N=1e5+5;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
ULL p[N],f[N],g[N];
char s0[N],s[N];
int n,m,T,ans;
int Hash1(int l,int r){return f[r]-f[l-1]*p[r-l+1];}
int Hash2(int l,int r){return g[r]-g[l-1]*p[r-l+1];}
int get_same(int l1,int l2,int r){
    int l=1,t=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(Hash1(l1,l1+mid-1)==Hash2(l2,l2+mid-1)) l=mid+1,t=mid;
        else r=mid-1;
    }
    return t;
}
bool init(int x){
    int l=x,l0=1,mb=m,r=x+m-1;
    for(int i=1;i<=3;i++){
        int c=get_same(l,l0,mb);
        l0+=c+1,l+=c+1,mb-=c;
        if(mb<=0) return 1;
    }
    return Hash1(l,r)==Hash2(l0,m);
}
signed main(){
	T=read();
    p[0]=1;
    for(int i=1;i<=1e5;i++) p[i]=p[i-1]*b;
    while(T--){
    ans=0;
    scanf("%s",s0+1);
    scanf("%s",s+1);
    n=strlen(s0+1),m=strlen(s+1);
    if(n<m){
        cout<<"0"<<endl;
        continue;
    }
    f[0]=g[0]=0;
	for(int i=1;i<=n;i++) f[i]=f[i-1]*b+s0[i];
    for(int i=1;i<=m;i++) g[i]=g[i-1]*b+s[i];
    for(int i=1;i+m-1<=n;i++){
        if(init(i))ans++;
    }
        printf("%d\n",ans);
	}   
	return 0;
}

样例过了但测试点过不了一个(并且下不到测试点),有没有人能帮忙一眼丁真一下我哪错了。

2023/11/10 01:07
加载中...