题目链接：http://poj.org/problem?id=1635
题意：给定两个由01组成的串，0代表远离根，1代表接近根。相当于每个串对应一个有根的树。然后让你判断2个串构成的树是否是同构的。
思路：首先根据01串构造出树，然后求树的最小表示法判断同构。 详情参照：https://www.byvoid.com/blog/directed-tree-bracket-sequence/
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long int LL;
const int MAXN=+;
int fa[MAXN];
char strA[MAXN],strB[MAXN];
vector<int>treeA[MAXN],treeB[MAXN];
void build(char *s,vector<int>tree[MAXN]){
int hashNum=,now=,len=strlen(s);
for(int i=;i<MAXN;i++){
tree[i].clear();
}
for(int i=;i<len;i++){
if(s[i]==''){
fa[hashNum]=now;
tree[now].push_back(hashNum);
now=hashNum++;
}
else{
now=fa[now];
}
}
}
string dfs(int now,vector<int>tree[MAXN]){
vector<string>HashC;
for(int i=;i<tree[now].size();i++){
HashC.push_back(dfs(tree[now][i],tree));
}
string Hash="(";
sort(HashC.begin(),HashC.end());
for(int i=;i<HashC.size();i++){
Hash+=HashC[i];
}
Hash+=")";
return Hash;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%s",strA); scanf("%s",strB);
memset(fa,,sizeof(fa));build(strA,treeA);
memset(fa,,sizeof(fa));build(strB,treeB);
if(dfs(,treeA)==dfs(,treeB)){
printf("same\n");
}
else{
printf("different\n");
}
}
return ;
}
思路2:HASH,思路参照：集训队论文：杨弋《Hash在信息学竞赛中的一类应用》
题目卡的比较死。 参数不好拿捏。最好进行Double HASH比较保险
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long int LL;
typedef unsigned int uint;
const int MAXN=+;
const int MODF=1e9+;
const int MODS=1e9+;
int fa[MAXN],HF[MAXN],HS[MAXN];
char strA[MAXN],strB[MAXN];
vector<int>treeA[MAXN],treeB[MAXN];
void build(char *s,vector<int>tree[MAXN]){
int hashNum=,now=,len=strlen(s);
for(int i=;i<MAXN;i++){
tree[i].clear();
}
for(int i=;i<len;i++){
if(s[i]==''){
fa[hashNum]=now;
tree[now].push_back(hashNum);
now=hashNum++;
}
else{
now=fa[now];
}
}
}
pair<int,int> dfs(int now,vector<int>tree[MAXN]){
int HashNumF=,HashNumS=;
vector<pair<int,int> >HashC;
for(int i=;i<tree[now].size();i++){
HashC.push_back(dfs(tree[now][i],tree));
}
sort(HashC.begin(),HashC.end());
for(int i=;i<HashC.size();i++){
HashNumF=((HashNumF^HashC[i].first)*HF[i])%MODF;
HashNumS=((HashNumS^HashC[i].second)*HS[i])%MODS;
}
return make_pair(HashNumF%MODF,HashNumS%MODS);
}
int main()
{
for(int i=;i<MAXN;i++){
HF[i]=rand()%MODF;
HS[i]=rand()%MODS;
}
int t;
scanf("%d",&t);
while(t--){
scanf("%s",strA); scanf("%s",strB);
memset(fa,,sizeof(fa));build(strA,treeA);
memset(fa,,sizeof(fa));build(strB,treeB);
pair<int,int>TA=dfs(,treeA);
pair<int,int>TB=dfs(,treeB);
if(TA.first==TB.first&&TA.second==TB.second){
printf("same\n");
}
else{
printf("different\n");
}
}
return ;
}