有根树同构。参考论文《hash在。。。。》
1 #include <iostream> 2 #include <fstream> 3 #include <algorithm> 4 #include <cstring> 5 #include <climits> 6 #include <cmath> 7 8 using namespace std; 9 10 const int leaf_hash=2099; 11 const int pt=9323; 12 const int qt=8719; 13 char str1[3100], str2[3100]; 14 char *p; 15 16 int Hash() 17 { 18 int sum=1; 19 if(*(p)=='1'&&*(p-1)=='0'){ 20 p++; 21 //cout<<"leaf_hash="<<endl; 22 return leaf_hash; 23 } 24 while(*p!=' ' && *p++ == '0')//这个巧妙的循环,把子节点的hash值都加给了父节点,作为父节点的hash值 25 { 26 //cout<<"for"<<endl; 27 sum = (sum*(pt^Hash()))%qt; 28 } 29 // printf("sum==%d ",sum); 30 return sum; 31 } 32 33 34 int main() 35 { 36 // freopen("input.txt", "r", stdin); 37 int T; 38 scanf("%d", &T); 39 while(T--) 40 { 41 scanf("%s%s", str1, str2); 42 p = str1; 43 int a = Hash(); 44 p = str2; 45 //cout<<a<<endl; 46 int b = Hash(); 47 //cout<<b<<endl; 48 if(a == b) 49 { 50 puts("same"); 51 } 52 else 53 { 54 puts("different"); 55 } 56 } 57 return 0; 58 }