几道字典树题目-白红宇

几道字典树题目

阅读量：5265 次

发布时间：2019-06-14

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

POJ 2418 Hardwood Species

题意：给一些字符串，按照字典序输出他们，并且输出频率...........

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                //形如INT_MAX一类的#define MAX 100005#define INF 0x7FFFFFFF#define REP(i,s,t) for(int i=(s);i<=(t);++i)#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define mp(a,b) make_pair(a,b)#define L(x) x<<1#define R(x) x<<1|1# define eps 1e-5//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂using namespace std;struct Trie { int next[128]; int sum; char s[33]; void init() { memset(next,0,sizeof(next)); sum = 0; }} a[301111];int num,cnt,root;char str[33];void insert(char *key) { int p = root; for(int i=0; key[i]; i++) { int t = int(key[i]); if(a[p].next[t] == 0) { a[p].next[t] = ++ num; a[num].init(); } p = a[p].next[t]; } a[p].sum ++; a[p].s[0] = '\0'; strcpy(a[p].s,key);}void dfs(int p) { if(a[p].sum != 0) { printf("%s ",a[p].s); printf("%.4f\n",(a[p].sum * 1.0) / cnt * 100); } for(int i=0; i<128; i++) { if(a[p].next[i] != 0) { int t = a[p].next[i]; dfs(t); } }}int main() { root = 0; num = 0; cnt = 0; a[root].init(); while(gets(str)) { int len = strlen(str); if(len == 0) break; cnt ++; insert(str); } dfs(0); return 0;}

HDU 2846 Repository

题意：给定一些单词作为字典，和一些单词作为询问，对于每个询问，求出它在所有字典单词中作为单词子串出现的次数（它只能在同一单词中以子串形式出现一次）

对于每个字典中的单词，让它所有后缀都在字典树中建树，这样只要在字典树中找前缀就等同于找到子串了

需要注意的是，它只能在同一单词中以子串形式出现一次，如：str：dddddd 则ddd在str中只出现一次，所以对于同一单词产生的后缀，需要判重......

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                //形如INT_MAX一类的#define MAX 100005#define INF 0x7FFFFFFF#define REP(i,s,t) for(int i=(s);i<=(t);++i)#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define mp(a,b) make_pair(a,b)#define L(x) x<<1#define R(x) x<<1|1# define eps 1e-5//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂using namespace std;int n,q,root,cnt;char str[22];char keyword[22];struct Trie { int next[26]; int num; int kind; void init() { memset(next,0,sizeof(next)); num = 0; kind = -1; }} a[1111111];void insert(char *key,int id,int kind) { int p = root; for(int i=id; key[i]; i++) { int t = key[i] - 'a'; if(a[p].next[t] == 0) { a[p].next[t] = ++cnt; a[cnt].init(); } p = a[p].next[t]; if(a[p].kind != kind) { a[p].kind = kind; a[p].num ++; } }}int query(char *key) { int p = root; int sum = 0; for(int i=0; key[i]; i++) { int t = key[i] - 'a'; if(a[p].next[t] == 0) return 0; p = a[p].next[t]; } sum += a[p].num; return sum;}int main() { root = 0; cnt = 0; scanf("%d",&n); for(int i=0; i

POJ 1204 Word Puzzles

题意：给定了一个1000 * 1000 的由大写字母组成的矩阵，现在给出一些单词，要求在矩阵中找到每个单词，记录首字母的位置，以及它沿着什么方向走（8个方向，米字型）

将单词建立字典树，然后在矩阵中枚举每个点作为起点，8个方向直接找就行了..........

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                //形如INT_MAX一类的#define MAX 100005#define INF 0x7FFFFFFF#define REP(i,s,t) for(int i=(s);i<=(t);++i)#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define mp(a,b) make_pair(a,b)#define L(x) x<<1#define R(x) x<<1|1# define eps 1e-5//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂using namespace std;int n,m,w;struct Word { int x,y,dir,kind; char word[1111];}s[1111];char str[1111][1111];int dx[] = {-1,-1,0,1,1,1,0,-1};int dy[] = {0,1,1,1,0,-1,-1,-1};int root , cnt ;struct Trie { int next[26]; int kind; void init() { memset(next,0,sizeof(next)); kind = -1; }}a[1111111];void insert(char *key, int kind) { int p = root; for(int i=0; key[i]; i++) { int t = key[i] - 'A'; if(a[p].next[t] == 0) { a[p].next[t] = ++ cnt; a[cnt].init(); } p = a[p].next[t]; } a[p].kind = kind;}void solve() { for(int i=0; i
                
                 = 0 && x < n && y >= 0 && y < m && p) { if(a[p].kind != -1) { s[a[p].kind].dir = k; s[a[p].kind].x = i; s[a[p].kind].y = j; } x = x + dx[k]; y = y + dy[k]; int t = str[x][y] - 'A'; p = a[p].next[t]; } } } } for(int i=0; i

待续.....

转载于:https://www.cnblogs.com/suncoolcat/p/3294108.html

你可能感兴趣的文章