首页 > 代码库 > hdu 2846 Repository (字典树)
hdu 2846 Repository (字典树)
//给定的字符串在模式串中出现的个数 # include <cstdio> # include <algorithm> # include <cstring> # include <iostream> using namespace std; # define MAX 26 typedef struct Trie_Node { int count;//记录包含该结点的单词个数 int id;//最后一次经过此结点的商品的id Trie_Node *next[MAX]; } Trie; void insert(Trie *root,char *s,int id) { Trie *p=root; while(*s!='\0') { if(p->next[*s-'a']==NULL) { Trie *temp=(Trie*)malloc(sizeof(Trie)); for(int i=0; i<MAX; i++) { temp->next[i]=NULL; } temp->count=0; temp->id=-1;//-1表示没有商品 p->next[*s-'a']=temp; } p=p->next[*s-'a']; if(p->id!=id) //如果当前结点的商品ID不等于要插入商品的ID,则计数器count++,并且重新置ID的值 { p->id=id; p->count++; } s++; } } int search(Trie *root,char *s) { Trie *p=root; for(int i=0; s[i]!='\0'; i++) { if(p->next[s[i]-'a']==NULL||p==NULL) return false; p=p->next[s[i]-'a']; } return p->count; } int main() { int i,j; int n,m; char s[21]; Trie *root=(Trie*)malloc(sizeof(Trie)); for(i=0; i<MAX; i++) { root->next[i]=NULL; } root->count=0; root->id=-1; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%s",s); for(j=0; j<strlen(s); j++) //将字符串X=X1X2...Xn的分别以X1,X2...Xn开头的后缀字符串插入到Trie树中 { insert(root,s+j,i); } } scanf("%d",&m); for(i=0; i<m; i++) { scanf("%s",s); printf("%d\n",search(root,s)); } return 0; }
hdu 2846 Repository (字典树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。