说明

该代码解决的问题是：给定一个样本字符串和其对应的二进制编码，确定是否存在唯一的二进制编码表（前缀编码），使得每个字母对应一个二进制编码，且编码之间互不为前缀。如果存在多个可能的编码表，则输出"多种编码表"；如果存在唯一的编码表，则按字母顺序输出编码表。

算法标签

• 回溯算法
• 前缀编码验证
• 字符串处理

解题思路

1. 输入处理：读取数据集的数量 N，然后逐个处理每个数据集。每个数据集包含样本字符串和对应的二进制编码。
2. 字母表大小计算：统计样本字符串中不同字母的数量，确定字母表的大小。
3. 回溯搜索编码表：使用回溯算法尝试所有可能的编码分配，确保编码是前缀编码且能正确解码样本字符串。
4. 验证编码表：检查生成的编码表是否满足前缀编码的条件，并确保整个编码空间被完全使用。
5. 输出结果：根据回溯结果输出唯一的编码表或"多种编码表"。

分析

• 回溯算法：通过递归尝试所有可能的编码分配，确保编码满足前缀条件和正确解码样本字符串。
• 前缀编码验证：在回溯过程中，检查新分配的编码是否与已有编码冲突（即是否为其他编码的前缀或反之）。
• 编码空间验证：确保所有可能的编码都被使用，没有未使用的编码空间。
• 字母顺序输出：对唯一的编码表按字母的ASCII值排序后输出。

实现步骤

1. 读取输入：读取数据集的数量 N，然后逐个处理每个数据集。
2. 统计字母表：计算样本字符串中不同字母的数量。
3. 回溯搜索：从二进制编码的开头开始，尝试为每个字母分配不同长度的编码，确保编码满足前缀条件。
4. 验证编码表：检查生成的编码表是否完全覆盖编码空间且无冲突。
5. 输出结果：根据回溯结果输出唯一的编码表或"多种编码表"。

代码

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <string>
#include <algorithm>

using namespace std;

typedef map<char, string> CodeTable;

int getAlphabetSize(const string& s) {
	unordered_set<char> chars;
	for (char c : s) {
		chars.insert(c);
	}
	return chars.size();
}

bool checkFullSpace(const CodeTable& codeTable) {
	unsigned int sum = 0;
	for (const auto& entry : codeTable) {
		int len = entry.second.size();
		if (len == 0) return false;
		sum += (0x80000000 >> len);
	}
	return sum == 0x80000000;
}

void backtrack(const string& orig, const string& coded, int alphaSize, CodeTable& codeTable, vector<CodeTable>& solutions) {
	if (orig.empty() && coded.empty()) {
		if (checkFullSpace(codeTable)) {
			solutions.push_back(codeTable);
		}
		return;
	}
	
	if (orig.empty() || coded.empty()) {
		return;
	}
	
	if (orig.size() > coded.size()) {
		return;
	}
	
	size_t minRequired = 0;
	for (char c : orig) {
		auto it = codeTable.find(c);
		if (it != codeTable.end()) {
			minRequired += it->second.size();
		} else {
			minRequired += 1;
		}
	}
	if (minRequired > coded.size()) {
		return;
	}
	
	char current = orig[0];
	auto it = codeTable.find(current);
	if (it != codeTable.end()) {
		const string& code = it->second;
		if (code.size() > coded.size()) {
			return;
		}
		if (coded.substr(0, code.size()) != code) {
			return;
		}
		string newOrig = orig.substr(1);
		string newCoded = coded.substr(code.size());
		
		while (!newOrig.empty()) {
			char lastChar = newOrig.back();
			auto itLast = codeTable.find(lastChar);
			if (itLast == codeTable.end()) {
				break;
			}
			const string& lastCode = itLast->second;
			if (lastCode.size() > newCoded.size()) {
				break;
			}
			string codedSuffix = newCoded.substr(newCoded.size() - lastCode.size());
			if (codedSuffix == lastCode) {
				newCoded = newCoded.substr(0, newCoded.size() - lastCode.size());
				newOrig = newOrig.substr(0, newOrig.size() - 1);
			} else {
				break;
			}
		}
		
		backtrack(newOrig, newCoded, alphaSize, codeTable, solutions);
	} else {
		int maxLen = min((int)coded.size(), alphaSize - 1);
		for (int len = 1; len <= maxLen; ++len) {
			string candidate = coded.substr(0, len);
			
			bool valid = true;
			for (const auto& entry : codeTable) {
				const string& existing = entry.second;
				if (existing.size() >= len) {
					if (existing.substr(0, len) == candidate) {
						valid = false;
						break;
					}
				} else {
					if (candidate.substr(0, existing.size()) == existing) {
						valid = false;
						break;
					}
				}
			}
			if (!valid) continue;
			
			codeTable[current] = candidate;
			string newOrig = orig.substr(1);
			string newCoded = coded.substr(len);
			
			while (!newOrig.empty()) {
				char lastChar = newOrig.back();
				auto itLast = codeTable.find(lastChar);
				if (itLast == codeTable.end()) {
					break;
				}
				const string& lastCode = itLast->second;
				if (lastCode.size() > newCoded.size()) {
					break;
				}
				string codedSuffix = newCoded.substr(newCoded.size() - lastCode.size());
				if (codedSuffix == lastCode) {
					newCoded = newCoded.substr(0, newCoded.size() - lastCode.size());
					newOrig = newOrig.substr(0, newOrig.size() - 1);
				} else {
					break;
				}
			}
			
			backtrack(newOrig, newCoded, alphaSize, codeTable, solutions);
			
			codeTable.erase(current);
			
			if (solutions.size() > 1) return;
		}
	}
}

void processDataset(int datasetNum, const string& original, const string& coded) {
	cout << "DATASET #" << datasetNum << endl;
	int alphaSize = getAlphabetSize(original);
	vector<CodeTable> solutions;
	CodeTable codeTable;
	
	backtrack(original, coded, alphaSize, codeTable, solutions);
	
	if (solutions.size() > 1) {
		cout << "MULTIPLE TABLES" << endl;
	} else if (solutions.size() == 1) {
		set<char> chars(original.begin(), original.end());
		for (char c : chars) {
			cout << c << " = " << solutions[0].at(c) << endl;
		}
	} else {
		cout << "MULTIPLE TABLES" << endl;
	}
}

int main() {
	int N;
	cin >> N;
	string dummy;
	getline(cin, dummy);
	for (int i = 1; i <= N; ++i) {
		string original, coded;
		getline(cin, original);
		getline(cin, coded);
		processDataset(i, original, coded);
	}
	return 0;
}