POJ 1451 T9

Trie树

POJ 1451 T9

题意：模拟用9个键的手机进行输入的，每输一个字母，输出最可能匹配的单词。

一开始想用链表储存所有的单词，写的时候才发现连链表维护，实在太麻烦了，而且效率又不高。

对于固定的输入，只用输出一个最可能匹配的词，所以不用保存所有的单词，只用保存频率最高的词就可以了。

两个单词的前缀可能重叠，所以要预处理，使任何单词或前缀只插入一次。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define MAXN 1010
  5 using namespace std;
  6 
  7 struct Word
  8 {
  9     char s[111];
 10     int t;
 11 };
 12 
 13 struct Trie
 14 {
 15     Trie *num[8];
 16     Word wo;
 17 };
 18 
 19 Trie root;
 20 Word w[1010];
 21 int c[1010][103];
 22 char key[]="22233344455566677778889999";
 23 
 24 void Add(Trie *node, char *s, int i, int j)
 25 {
 26     if(j>0&&c[i][j-1])
 27     {
 28         s[j]='\0';
 29         if(node->wo.t<c[i][j-1])
 30         {
 31             strcpy(node->wo.s,s);
 32             node->wo.t=c[i][j-1];
 33         }
 34     }
 35     s[j]=w[i].s[j];
 36     if(s[j]=='\0')
 37         return ;
 38         
 39     int d,k=key[w[i].s[j]-'a']-'2';
 40     if(!node->num[k])
 41     {
 42         node->num[k] = new Trie[8];
 43             for(d=0;d<8;d++)
 44         node->num[k]->num[d]=NULL;
 45         node->num[k]->wo.t=0;
 46     }
 47 
 48     Add(node->num[k],s,i,j+1);
 49 }
 50 
 51 void Construct()
 52 {
 53     int n,i,k,j;
 54     char s[103];
 55     memset(c,0,sizeof(c));
 56     for(i=0;i<8;i++)
 57         root.num[i]=NULL;
 58     root.wo.t=0;
 59     
 60     scanf("%d",&n);
 61     for(i=0;i<n;i++)
 62         scanf("%s%d",w[i].s,&w[i].t);
 63     for(i=0;i<n;i++)
 64         for(j=0,k=(int)strlen(w[i].s);j<k;j++)
 65             c[i][j]=w[i].t;
 66     for(i=n-2;i>=0;i--)
 67     {
 68         for(j=0;w[i].s[j]!='\0';j++)
 69             if(w[i].s[j]==w[i+1].s[j])
 70             {
 71                 c[i][j]+=c[i+1][j];
 72                 c[i+1][j]=0;
 73             }
 74             else
 75                 break;
 76     }
 77     for(i=0;i<n;i++)
 78         Add(&root,s,i,0);
 79 }
 80 
 81 void Query(Trie *node, char *s, int j)
 82 {
 83     if(node==NULL||node->wo.t==0)
 84     {
 85         for(;s[j]!='1';j++)
 86             puts("MANUALLY");
 87         return;
 88     }
 89     puts(node->wo.s);
 90     j++;
 91     if(s[j]=='1')
 92         return ;
 93     Query(node->num[s[j]-'2'],s,j);
 94 }
 95 
 96 void Solve()
 97 {
 98     int m,i,j;
 99     char s[201];
100     scanf("%d",&m);
101     while(m--)
102     {
103         scanf("%s",s);
104         if(s[0]!='1')
105             Query(root.num[s[0]-'2'],s,0);
106         puts("");
107     }
108 }
109 
110 void Trans(Trie *node)
111 {
112     int i;
113     for(i=0;i<8;i++)
114         if(node->num[i])
115         {
116             Trans(node->num[i]);
117             free(node->num[i]);
118         }
119 }
120 
121 void Destroy()
122 {
123     int i;
124     for(i=0;i<8;i++)
125         if(root.num[i])
126         {
127             Trans(root.num[i]);
128             free(root.num[i]);
129         }
130 }
131 
132 int main()
133 {
134     int T,k;
135     scanf("%d",&T);
136     for(k=1;k<=T;k++)
137     {
138         Construct();
139         printf("Scenario #%d:\n",k);
140         Solve();
141         puts("");
142         Destroy();
143     }
144     return 0;
145 }