首页 > 代码库 > POJ 1635 Subway tree systems Hash法判断有根树是否同构
POJ 1635 Subway tree systems Hash法判断有根树是否同构
Hash在信息学竞赛中的一类应用 中的某道例题
"不难想到的算法是使用两个字符串分别表示两棵树，但是如果使用Hash的话应该怎么做呢？
可以使用一种类似树状递推的方法来计算Hash值：
对于一个节点v，先求出它所有儿子节点的Hash值，并从小到大排序，记作H1，H2，„，HD。那么v的Hash值就可以计算为：
(（(a * p) ^ H1 mod q) * p ^ H2 mod q).....
换句话说，就是从某个常数开始，每次乘以p，和一个元素异或，再除以q取余，再乘以p，和下一个元素异或，除以q取余„„一直进行到最后一个元素为止。最后把所得到的结果乘以b，再对q取余。"
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 3005;const int C = 12345, p = 67890, q = 1e9 + 7;char str1[maxn], str2[maxn];VI ch[maxn], hash[maxn];int fa[maxn];int dfs(int now) { int m = ch[now].size(); if(m == 0) return C; for(int i = 0;i < m;i++) { hash[now].PB(dfs(ch[now][i])); } sort(hash[now].begin(),hash[now].end()); int ret = C; for(int i = 0;i < m;i++) { ret = (ret * p) ^ hash[now][i] % q; } return ret;}int gethash(char *str) { memset(fa,0,sizeof(fa)); int len = strlen(str), u = 0, sz = 1; for(int i = 0;i < len;i++) { ch[i].clear(); hash[i].clear(); } for(int i = 0;i < len;i++) { if(str[i] == ‘0‘) { ch[u].PB(sz); fa[sz] = u; u = sz++; } else { u = fa[u]; } } return dfs(0);}int main() { int T; scanf("%d",&T); while(T--) { scanf("%s%s",str1,str2); if(gethash(str1) == gethash(str2)) { puts("same"); } else puts("different"); } return 0;}
POJ 1635 Subway tree systems Hash法判断有根树是否同构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。