Repository-白红宇

Repository

阅读量：6332 次

发布时间：2019-06-22

本文共 3069 字，大约阅读时间需要 10 分钟。

Repository

When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.

InputThere is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it's length isn't beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.OutputFor each query, you just output the number of the merchandises, whose names contain the search string as their substrings.

Sample Input

20adaeafagahaiajakaladsaddadeadfadgadhadiadjadkadlaes5badads

Sample Output

02011112 题意：给你一堆食品的名字，然后再给你一堆要查询的数据，实际就是求以某个串为子串的串的个数

分析：前面写的那道题就是关于字典树前缀的问题，这个就不一样了，，我刚开始想的是把整个字典树遍历一次，我从根节点出发，然后哪个不为NULL，我就往前走，直到走到不能走就不找了，想着想着就把自己绕进去了，然后尝试着按自己的想法写代码，总觉得存在一些问题，最后还是百度看了一下别人的想法，觉得知道了这个想法之后去实现还是挺简单的，但是我想不到这个想法啊！要查的是以某个串为子串的串的个数 可以发现  ，一个串的任何子串肯定是这个串某个后缀的前缀，还要注意一点，就是已经建立在字典树上的同一个字符串的子串不要重复计数，所以就可以设置一个flag，用于判断是否重复计数；如"ri"是“Trie" 的子串  是后缀 "rie" 的前缀 ，那么我们在向Trie中插入时可以把这个串的所有后缀都插入 插入时要注意来自同一个串的后缀的相同前缀只能统计一次  如 "abab" 这个串  "ab" 既是后缀 "abab" 的前缀  也是后缀 "ab" 的前缀  但是只能统计一次

AC代码：

//#include    
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          #include 
                          
                           #include 
                           
                            #include 
                            
                             #include 
                             
                              #include 
                              
                               #include 
                               
                                #define N 500005#define mem(a,b) memset(a,b,sizeof(a))#define IOS ios::sync_with_stdio(false)#define INF 1000000010template
                                
                                  inline T max(T a,T b,T c){ return max(a,max(b,c));}template
                                 
                                   inline T min(T a,T b,T c){ return min(a,min(b,c));}template
                                  
                                    inline T max(T a,T b,T c,T d){ return max(a,max(b,c,d));}template
                                   
                                     inline T min(T a,T b,T c,T d){ return min(a,min(b,c,d));}const int dx[]={ 0,1,0,-1,0,1,-1,1,-1};const int dy[]={ 0,0,1,0,-1,1,-1,-1,1};typedef long long ll;using namespace std;//coding...........................char a[N];struct node{ int cnt; int flag=0; //标记 struct node *next[26]; node() { cnt=0; mem(next,0); }}*root;void buildtrie(char *s,node *root,int flag){ int len=strlen(s); int t; for (int i=0;i
                                    
                                     next[t]==NULL) root->next[t]=new node(); root=root->next[t]; if (root->flag!=flag) { root->flag=flag; root->cnt++; } }}int Findtrie(char *s,node *root) //查找{ int len=strlen(s); int t; for (int i=0;i
                                     
                                      next[t]==NULL) return 0; root=root->next[t]; } return root->cnt;}int main(){ int n,m; root=new node(); cin>>n; for (int ww=1;ww<=n;ww++) { scanf("%s",a); int len=strlen(a); for (int i=0;i
                                      
                                       >m; while (m--) { scanf("%s",a); cout << Findtrie(a,root) << endl; }}

转载于:https://www.cnblogs.com/lisijie/p/7922411.html

你可能感兴趣的文章