【uva 12219】Common Subexpression Elimination（图论–树+自定义比较器+映射+递归）

题意：如题，用表达式树来表示一个表达式，且消除公共的部分，即用编号表示。编号 K 定义为表达式第 K 个出现的字符串。

解法：先构造表达式树，给每棵子树用(string,left_son,right_son)–>(哈希值,…,…)编号。由于最多出现4个小写字母，所以可以用27进制数表示，同时也要利用好映射map的count(),和对应的dict[]的编号。

再递归输出表达式，利用编号的定义，看输出编号或字符串。

注意——这里的自定义比较器用的是“显式定义”，若是2个键值排序，还可以用专门把2个类型捆绑到一起的pair，它默认先比较第一关键字 .first，再是第二关键字 .second——

定义排序：typedef pair<int,int> pii[]; 再加优先队列 或 cmp函数
赋值： pii[]=make_pair(x,y);

P.S.我是参考着紫书做着Rujia Liu的代码打着，但如名，我这konjac蒟蒻改成了一个我自己能够记得的代码~所以，这题主要是提高代码能力，hh~

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<map>
 5 #include<iostream>
 6 using namespace std;
 7 const int N=50010;
 8
 9 char ss[7*N];
10 struct node
11 {
12     char s[6];
13     int hash,lc,rc,l;
14     bool operator < (const node& x) const
15     {
16       if (hash!=x.hash) return hash<x.hash;
17       if (lc!=x.lc) return lc<x.lc;
18       return rc<x.rc;
19     }
20 }a[N];
21 map<node,int> dict;
22 bool v[N];
23 int len,p;
24
25 int build()
26 {
27     int id=++len,t=p;
28     node& u=a[id];
29     u.hash=0,u.lc=u.rc=-1,u.l=0;
30     while (ss[p]>='a'&&ss[p]<='z')
31     {
32       u.hash=27*u.hash+ss[p]-'a'+1;
33       u.s[p-t+1]=ss[p];
34       p++;
35     }
36     u.l=p-t;
37     if (ss[p]=='(')
38     {
39       p++,u.lc=build();
40       p++,u.rc=build();
41       p++;
42     }
43     if (dict.count(u)) {len--;return dict[u];}
44     dict[u]=id;
45     return dict[u];
46 }
47
48 void print(int x)
49 {
50     if (v[x]) {printf("%d",x);return;}
51     v[x]=1;
52     for (int i=1;i<=a[x].l;i++) printf("%c",a[x].s[i]);
53     if (a[x].lc!=-1)
54     {
55       printf("(");
56       print(a[x].lc);
57       printf(",");
58       print(a[x].rc);
59       printf(")");
60     }
61 }
62
63 int main()
64 {
65     int T;
66     scanf("%d",&T);
67     while (T--)
68     {
69       len=0,p=1;
70       dict.clear();
71       scanf("%s",ss+1);
72       memset(v,0,sizeof(v));
73       print(build());
74       printf("\n");
75     }
76     return 0;
77 }