字典树模板代码求调
查看原帖
字典树模板代码求调
967198
jimeikun_sunxuhao楼主2023/5/26 08:13

这是题解:

#include<bits/stdc++.h>
using namespace std;
int T,q,n,t[3000005][65],cnt[3000005],idx;
char s[3000005];
int getnum(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
} 
void insert(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
    }
}
int find(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            return 0;
        p=t[p][c];
    }
    return cnt[p];
}
int main(){
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<=idx;i++)
            for(int j=0;j<=122;j++)
                t[i][j]=0;
        for(int i=0;i<=idx;i++)
            cnt[i]=0;
        idx=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            insert(s);
        }
        for(int i=1;i<=q;i++){
            scanf("%s",s);
            printf("%d\n",find(s));
        }
    }
    return 0;
}

这是我的代码:

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define loop(i,x,y) for(long long i=x;i<=y;i++)
#define doop(i,x,y) for(long long i=x;i>=y;i--)
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
#define ll long long
using namespace std;
const int N=3e6+10;
char s[N];int t,n,q;
int zds[N][65],flag[N],tot;
int read(){int x=0,y=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') y=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch^48);    ch=getchar();}return x*y;}
int qpow(int a,int b,int mm){int sum=1;while(b){if(b&1)sum=sum*a%mm;a=a*a%mm;b>>=1;}return sum;}
int getnum(char xx){if(xx>='A'&&xx<='Z')return xx-'A';else if(xx>='a'&&xx<='z')return xx-'a'+26;else return xx-'0'+52;} 
void insert(char *a) {
	int u=0,b=strlen(a);
	for(int i=0;i<b;i++){
		int c=getnum(a[i]);
		if(!zds[u][c])zds[u][c]=tot++;
		u=zds[u][c];flag[u]++;
	}
}
int find(char *a){
	int u=0,b=strlen(a);
	for(int i=0;i<b;i++){
		int c=getnum(a[i]);
		if(!zds[u][c])return 0;
		u=zds[u][c]; 
	}
	return flag[u];
}
int main()
{
    t=read();
    while(t--){
    	scanf("%d%d",&n,&q);
    	loop(i,0,tot){
    		loop(j,0,122)zds[i][j]=0;
		}
        loop(i,0,tot)flag[i]=0; tot=0;
        loop(i,1,n){
        	scanf("%s",s);
        	insert(s);
		}
		loop(i,1,q){
			scanf("%s",s);
			printf("%d\n",find(s));
		}
	}
    return 0;
}

我的代码是按着这个题解改的,感觉基本没啥区别了啊(再改就一样了啊),可为什么我连样例都过不了

(还有为啥题解的数组没越界啊

2023/5/26 08:13
加载中...