本文共 1072 字，大约阅读时间需要 3 分钟。
题目大意：给出一段表达式，并让其中的重复部分用序号来代替
思路：首先针对表达式构建出表达式树，对于出现过了的子树用map储存，再在打印时用一个vis数组来记录这个序号的子树是否打印过了，如果已经打印过了，那么就打印其序号。
AC代码：
#include #include #include #include #include using namespace std;const int size=1e6+5;struct node{ int Hash; int l; int r; string s; node(int Hash=0,int l=-1,int r=-1,string s=""):Hash(Hash),l(l),r(r),s(s){} friend bool operator<(node a,node b) { if(a.Hash!=b.Hash) return a.Hash mp;int p=0;int cnt;string ori;int build(){ int id=cnt++; Node[id].Hash=0; Node[id].l=-1; Node[id].r=-1; Node[id].s=""; while(ori[p]>='a'&&ori[p]<='z'){ Node[id].Hash=Node[id].Hash*26+ori[p]-'a'+1; Node[id].s.push_back(ori[p]); p++; } if(ori[p]=='(') { p++; Node[id].l=build(),p++; Node[id].r=build(),p++; } if(mp.count(Node[id])){ cnt--; return mp[Node[id]]; } return mp[Node[id]]=id;}void print(int id){ if(vis[id]){ printf("%d",id+1); return ; } vis[id]=true; cout< >ori; print(build()); cout<
转载于:https://www.cnblogs.com/fly-white/p/10092712.html
