本文主要是介绍Repository HDU - 2846(字典树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Repository
题目链接：HDU - 2846题意：给出P个字符串，找出其子串包含s的字符串的个数；
思路：暴力首先排除，还学过什么找子串的？KMP，只有一条串可以，本题串太多;AC自动机，匹配单主串，多匹配串，显然也不合适；在想想，好像没有了；不对，还有一个字典树可以匹配多个串，不过只能找前缀，，，
其实子串一定是该串某一后缀的前缀，那么把后缀存进去就可以了；
还有一个问题，后缀重复怎么办？像aaaa，？
在存串的时候同时把标号存进去，标号相同说明之前存过，数量就不需要增加了；
还有，本题用c++交，G++MEL； #include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
struct Trie{int cnt, ID;Trie* next[26];Trie(){cnt=0;ID=-1;for(int i=0; i<26; i++){next[i]=NULL;}}
}root;
void create(char *s, int ID){Trie *p=&root;int len=strlen(s);for(int i=0; i<len; i++){int id=s[i]-'a';if(p->next[id]==NULL){p->next[id]=new Trie;//p->next[id]->cnt++;}p=p->next[id];if(p->ID!=ID) p->cnt++;p->ID=ID;}
}
int find(char *s){Trie *p=&root;int len=strlen(s);for(int i=0; i<len; i++){int id=s[i]-'a';if(p->next[id]==NULL) return 0;p=p->next[id];}return p->cnt;
}
int main(){int P, Q;scanf("%d", &P);while(P--){char s[30];scanf("%s", s);int len=strlen(s);for(int i=0; i<len; i++){create(s+i, P);}}scanf("%d", &Q);while(Q--){char s[30];scanf("%s", s);printf("%d\n", find(s));}return 0;
}这篇关于Repository HDU - 2846(字典树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
