#include <iostream> #include <string> using namespace std; int lefts[20], rights[20], father[20]; string s1, s2, s3; int n, ans; void calc(int x, int dep) { ans = ans + dep * (s1[x] - 'A' + 1); if (lefts[x] >= 0) calc(lefts[x], dep + 1); if (rights[x] >= 0) calc(rights[x], dep + 1); } void check(int x) { if (lefts[x] >= 0) check(lefts[x]); s3 = s3 + s1[x]; if (rights[x] >= 0) check(rights[x]); } void dfs(int x, int th) { if (th == n) { s3 = ""; check(0); if (s3 == s2) { ans = 0; calc(0, 1); cout << ans << endl; } return; } if (lefts[x] == -1 && rights[x] == -1) { lefts[x] = th; father[th] = x; dfs(th, th + 1); father[th] = -1; lefts[x] = -1; } if (rights[x] == -1) { rights[x] = th; father[th] = x; dfs(th, th + 1); father[th] = -1; rights[x] = -1; } if (father[x] >= 0) dfs(father[x], th); } int main( ) { cin >> s1; cin >> s2; n = s1.size( ); memset(lefts, -1, sizeof(lefts)); memset(rights, -1, sizeof(rights)); memset(father, -1, sizeof(father)); dfs(0, 1); }
输入:
ABCDEF
BCAEDF
输出:___1_______