正题

评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P2580

---

题目大意

给n个字符串，用m个字符串和他们匹配，分为错误匹配,重复匹配,正确匹配。

---

解题思路

裸的TrieTrie(字典树)

---

code

#include<cstdio> #include<cstring> using namespace std; int n,tot,m,l[800000][26];; char s[101]; bool pre[800000],ok[800000]; void insert(char *s)//插入 {int len=strlen(s),now=0;for(int i=0;i<len;i++){int ch=s[i]-'a';if(!l[now][ch]) l[now][ch]=++tot;//新建节点now=l[now][ch];//下一个点}pre[now]=true;return; } void find(char *s) {int len=strlen(s),now=0;for(int i=0;i<len;i++){int ch=s[i]-'a';if(!l[now][ch])//错误匹配{printf("WRONG\n");return;}now=l[now][ch];}if(!pre[now]) printf("WRONG\n");//错误匹配else if(ok[now]) printf("REPEAT\n");//重复匹配else {printf("OK\n");ok[now]=true;}//正确匹配和标记return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s);insert(s);}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%s",s);find(s);}return 0; }

总结

以上是生活随笔为你收集整理的P2580-于是他错误的点名开始了【Trie,字符串】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。