根据最长公共后缀子串对字符串进行分组的教程

本教程旨在解决如何根据字符串的最长公共后缀子串（特别是域名/子域名结构）对一组字符串进行高效分组的问题。我们将通过一个JavaScript函数示例，详细解析其实现逻辑，包括如何识别子域名关系、构建分组字典，并确保每个字符串被精确地归类到其最长的匹配后缀子串下，从而生成一个结构化、易于理解的分组结果。

1. 问题描述：按最长公共后缀子串分组字符串

在处理诸如域名列表等字符串数据时，我们经常需要根据它们的最长公共后缀子串进行分组。例如，给定一个域名列表 [“samsung.phone.com”, “lg.phone.com”, “phone.com”, “camera.dsrl.nikon.com”, “amd.gpu.com”, “intel.cpu.com”]，我们的目标是创建一个字典（或映射），其中键是作为组标识的最长公共后缀子串，值是匹配该后缀的原始字符串列表。

这里的“最长公共后缀子串”特指那些在原始列表中也作为独立项出现的、且能作为其他字符串的后缀的子串。例如：

• “samsung.phone.com” 和 “lg.phone.com” 都以 “phone.com” 结尾，且 “phone.com” 也在列表中，因此它们应归类到 “phone.com” 组。
• 如果添加 “cpu.com”，则 “intel.cpu.com” 应归类到 “cpu.com” 组。
• 如果添加 “hello.samsung.phone.com”，并且 “samsung.phone.com” 也在列表中，那么 “hello.samsung.phone.com” 应该归类到 “samsung.phone.com” 组，而不是更短的 “phone.com” 组，因为 “samsung.phone.com” 是更长的匹配后缀。

最终输出的字典结构应如下所示：

{
"phone.com": ["lg.phone.com", "samsung.phone.com"],
"camera.dsrl.nikon.com": [],
"amd.gpu.com": [],
"intel.cpu.com": []
}

注意，如果一个字符串本身没有更长的字符串以其作为后缀，它将作为键存在，但其值列表可能为空。

2. 解决方案：基于子域名的分组算法

我们将通过一个JavaScript函数 filterBySubdomain 来实现这一分组逻辑。该函数接收一个字符串列表，并返回一个分组字典。

2.1 核心算法解析

该算法分多个步骤进行，以确保准确地识别和分组字符串：

1. 初始化字典：
   创建一个空字典 dict，并将输入列表 domList 中的每个字符串作为键，初始化其值为一个空数组。这一步确保所有潜在的分组键都存在。

   const dict = {}; // key: subdomain, value: list of domains
   domList.forEach((el) => (dict[el] = []));

2. 识别直接子域名关系：
   通过嵌套循环遍历 domList。对于每一对不同的字符串 domList[i] 和 domList[j]，检查 domList[j] 是否以 domList[i] 作为其“子域名”部分。这里的“子域名”被定义为 domList[j] 中第一个点号 . 之后的部分。如果匹配，则将 domList[j] 添加到 dict[domList[i]] 的列表中。

   for (let i = 0; i < domList.length; i++) {
   for (let j = 0; j < domList.length; j++) {
   if (i !== j) {
   const subdomain = domList[j].substring(domList[j].indexOf(".") + 1);
   if (subdomain === domList[i]) {
   dict[domList[i]].push(domList[j]);
   }
   }
   }
   }

   例如，如果 domList[j] 是 “samsung.phone.com”，domList[i] 是 “phone.com”，那么 subdomain 将是 “phone.com”，匹配成功，”samsung.phone.com” 会被添加到 dict[“phone.com”] 中。

3. 识别并收集所有已分组的域名：
   遍历当前 dict，将所有作为值列表中的域名收集到一个 mergedDomainList 中。这个列表包含了所有被识别为某个键的“子域名”的字符串。

   let mergedDomainList = [];
   for (const [subdomain, domainList] of Object.entries(dict)) {
   mergedDomainList = [...mergedDomainList, ...domainList];
   }

4. 移除不作为分组键的项：
   遍历 mergedDomainList。如果一个字符串 x 在 dict 中作为键存在，但其值列表 dict[x] 为空（即它没有其他字符串以它为直接子域名），那么它就不应该成为一个分组键。因此，将其从 dict 中删除。这一步用于清理那些虽然存在于原始列表但实际上没有扮演“分组中心”角色的字符串。

   mergedDomainList.forEach((x) => {
   if (dict[x] && dict[x].length === 0) delete dict[x];
   });

   例如，如果 intel.cpu.com 没有其他字符串以它为子域名，且 cpu.com 存在并成功分组了 intel.cpu.com，那么 intel.cpu.com 就不应再作为一个空键存在。

5. 精炼分组列表以确保最长后缀匹配：
   这是最关键的一步，用于实现“最长公共后缀子串”的逻辑。
   首先，获取当前 dict 中所有剩余的键（它们是最终的分组标识）。
   然后，对于 dict 中的每一个键值对，筛选其值列表：只保留那些不是当前 dict 中任何其他键的字符串。这意味着如果 samsung.phone.com 已经是一个键，那么 hello.samsung.phone.com 应该被分组到 samsung.phone.com 下，而不是 phone.com 下。通过将 samsung.phone.com 从 phone.com 的值列表中移除，我们确保了更长的后缀匹配优先。

   const toRemove = Object.keys(dict); // 最终作为分组键的列表
   for (const [key, value] of Object.entries(dict)) {
   dict[key] = value.filter(function (el) {
   return !toRemove.includes(el); // 移除那些本身也是分组键的字符串
   });
   }

2.2 示例代码

/**
* 根据最长公共后缀子串（子域名）对字符串列表进行分组。
* @param {string[]} domList 包含域名和子域名的字符串列表。
* @returns {Object.<string, string[]>} 一个字典，键为子域名，值为对应的域名列表。
*/
function filterBySubdomain(domList) {
const dict = {}; // 键: 子域名, 值: 对应的域名列表
// 1. 初始化字典：将所有输入字符串作为潜在键，值为空列表
domList.forEach((el) => (dict[el] = []));
// 2. 识别直接子域名关系
// 遍历所有字符串，查找哪些字符串是另一个字符串的直接子域名
for (let i = 0; i < domList.length; i++) {
for (let j = 0; j < domList.length; j++) {
if (i !== j) {
// 提取 domList[j] 的子域名部分（第一个点号之后的部分）
const firstDotIndex = domList[j].indexOf(".");
if (firstDotIndex === -1) continue; // 如果没有点号，则不构成子域名关系
const subdomain = domList[j].substring(firstDotIndex + 1);
if (subdomain === domList[i]) {
// 如果 domList[i] 是 domList[j] 的子域名
dict[domList[i]].push(domList[j]);
}
}
}
}
// 3. 收集所有已被分组的域名
let mergedDomainList = [];
for (const [subdomain, domainList] of Object.entries(dict)) {
mergedDomainList = [...mergedDomainList, ...domainList];
}
// 4. 移除那些作为键但其值列表为空的项（即它们本身没有子域名）
mergedDomainList.forEach((x) => {
// 检查 x 是否存在于 dict 且其值列表为空
if (dict.hasOwnProperty(x) && dict[x].length === 0) {
delete dict[x];
}
});
// 5. 精炼分组列表，确保最长后缀匹配原则
// 获取当前所有有效的分组键（子域名）
const finalKeys = Object.keys(dict);
for (const [key, value] of Object.entries(dict)) {
// 过滤掉值列表中那些本身也是最终分组键的字符串
// 这确保了例如 "hello.samsung.phone.com" 会被分组到 "samsung.phone.com"
// 而不是更通用的 "phone.com"
dict[key] = value.filter(function (el) {
return !finalKeys.includes(el);
});
}
return dict;
}

2.3 使用示例

// 示例输入数据
const x1 = [
"samsung.phone.com",
"lg.phone.com",
"phone.com",
"camera.dsrl.nikon.com",
"amd.gpu.com",
"intel.cpu.com",
];
const x2 = [
"samsung.phone.com",
"lg.phone.com",
"phone.com",
"camera.dsrl.nikon.com",
"amd.gpu.com",
"intel.cpu.com",
"cpu.com", // 新增项
];
const x3 = [
"samsung.phone.com",
"lg.phone.com",
"phone.com",
"camera.dsrl.nikon.com",
"amd.gpu.com",
"intel.cpu.com",
"cpu.com",
"hello.samsung.phone.com", // 新增项
];
// 调用函数进行分组
const result1 = filterBySubdomain(x1);
const result2 = filterBySubdomain(x2);
const result3 = filterBySubdomain(x3);
// 打印结果
console.log("--- 示例 1 ---");
console.log(result1);
console.log("\n--- 示例 2 ---");
console.log(result2);
console.log("\n--- 示例 3 ---");
console.log(result3);

2.4 预期输出

--- 示例 1 ---
{
'phone.com': [ 'samsung.phone.com', 'lg.phone.com' ],
'camera.dsrl.nikon.com': [],
'amd.gpu.com': [],
'intel.cpu.com': []
}
--- 示例 2 ---
{
'phone.com': [ 'samsung.phone.com', 'lg.phone.com' ],
'camera.dsrl.nikon.com': [],
'amd.gpu.com': [],
'cpu.com': [ 'intel.cpu.com' ]
}
--- 示例 3 ---
{
'samsung.phone.com': [ 'hello.samsung.phone.com' ],
'phone.com': [ 'lg.phone.com' ],
'camera.dsrl.nikon.com': [],
'amd.gpu.com': [],
'cpu.com': [ 'intel.cpu.com' ]
}

3. 注意事项与总结

• 性能考量： 该算法涉及多层循环和数组操作，对于非常大的输入列表，其时间复杂度可能较高。具体来说，嵌套循环识别子域名关系是 O(N^2)，后续的数组操作也会增加开销。在处理海量数据时，可能需要考虑更优化的数据结构或算法，例如使用Trie树（前缀树）来加速后缀匹配。
• “子域名”的定义： 本教程中的“子域名”特指第一个点号之后的部分。如果你的“最长公共后缀子串”定义不同（例如，不限于点号分隔，或需要考虑更复杂的模式），则需要修改 substring(domList[j].indexOf(“.”) + 1) 这一部分逻辑。
• 空列表处理： 如果一个键最终对应的列表为空，这意味着该键本身存在于原始输入中，但没有其他字符串以其作为最长公共后缀。这符合问题要求，即即使没有匹配项，该键也应存在。
• 调试技巧： 理解此类多步骤算法的最佳方法是在关键步骤设置断点，并使用 console.log 输出中间状态，逐步观察数据的变化。

通过上述 filterBySubdomain 函数，我们能够有效地根据最长公共后缀子串对字符串进行分组，尤其适用于域名或类似结构的数据整理。该方法清晰地定义了分组规则，并通过多阶段处理确保了结果的准确性和一致性。