#trie#洛谷 2580 于是他错误的点名开始了

本文主要是介绍#trie#洛谷 2580 于是他错误的点名开始了，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

trie模板题，询问存不存在，有没有重复询问

---

分析

因为容易理解，贴伪代码

void pusht(char *s){int len=strlen(s),p=1;for (register int k=0;k<len;k++){int c=s[k]-97;if (!trie[p][c]) trie[p][c]=++tot;p=trie[p][c];}end[p]=1;
}
int search(char *s){int len=strlen(s),p=1;for (int k=0;k<len;k++){p=trie[p][s[k]-97];if (!p) return 0;}return end[p];
}

---

代码

#include <cstdio>
#include <cstring>
int trie[500001][26],tot,n,end[500001]; char s[51];
void pusht(char *s){int len=strlen(s),p=1;for (register int k=0;k<len;k++){int c=s[k]-97;if (!trie[p][c]) trie[p][c]=++tot;//新建点p=trie[p][c];}end[p]=1;
}
int search(char *s){int len=strlen(s),p=1;for (int k=0;k<len;k++){p=trie[p][s[k]-97];//下一个位置if (!p) return 0;}if (end[p]) end[p]++;//同时用来累计次数return end[p]-1;
}
int main(){scanf("%d\n",&n);while (n--){scanf("%s",s+1);pusht(s+1);}scanf("%d\n",&n);while (n--){scanf("%s",s+1);int flag=search(s+1);if (flag<1) puts("WRONG");//不存在else if (flag==1) puts("OK");//只询问1次else puts("REPEAT"); //重复询问}return 0;
}

这篇关于#trie#洛谷 2580 于是他错误的点名开始了的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---