当前位置 博文首页 > 文章内容

    Trie树

    作者: 栏目:未分类 时间:2020-09-29 17:01:29

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    \(Trie\)

    今天搞了不少的好东西,正好趁热整理一下。

    \(Trie\)树:

    \(Trie\)树,其实就是一种专门用来存储字符串的树型结构。

    其基本代码与链式前向星相似。

    能够将建树和查询的复杂度降低到一个非常友善的地步:

    void add (char c[]){
    	int len=strlen(c+1);
    	int t=0;
    	for(int i=1;i<=len;i++){
    		if(!f[t][c[i]-'a']) f[t][c[i]-'a']=++cnt;
    		t=f[t][c[i]-'a'];
    	}
    	cd[t]=1;
    }
    

    建树操作。

    看吧~与链式前向星特别相似\(qwq\)

    以及…… 

    \(Trie\)树的模板题:

    P2580于是他错误的点名开始了

    \(AC\)代码

    #include<bits/stdc++.h>
    using namespace std;
    
    int n,m,cnt;
    char name[50001],report[500001],vis[500001];
    int f[500001][30];
    int cd[500001];
    
    void add (char c[]){
    	int len=strlen(c+1);
    	int t=0;
    	for(int i=1;i<=len;i++){
    		if(!f[t][c[i]-'a']) f[t][c[i]-'a']=++cnt;
    		t=f[t][c[i]-'a'];
    	}
    	cd[t]=1;
    }
    
    void check(char c[]){
    	int len=strlen(c+1);
    	int t=0;
    	for(int i=1;i<=len;i++){
    		t=f[t][c[i]-'a'];
    		if(!t){
    			printf("WRONG\n");
    			return;
    		}
    		
    	}
    	if(!vis[t]&&cd[t]){ printf("OK\n");vis[t]=1;return;}
    	if(!cd[t]) {printf("WRONG\n");return ;}
    	if(vis[t]) {printf("REPEAT\n");return;}
    		
    }
    
    int main(){
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%s",name+1);
    		add(name);
    	}
    	scanf("%d",&m);
    	for(int i=1;i<=m;i++){
    		scanf("%s",report+1);
    		check(report);
    	}
    	return 0;
    }
    

    详细题解

    另外:洛谷的测试数据特别特别的水。

    举个栗子:

    对于一个学生:\(asdfo\)

    如果老师念了\(asd\)

    那么显然我们应该输出\(WRONG\)

    但是!!!

    我们输出\(REPEAT\)也能$AC

    当然我的代码没有这个问题。