最长公共后缀分组教程全解析

今日不肯埋头，明日何以抬头！每日一句努力自己的话哈哈~哈喽，今天我将给大家带来一篇《最长公共后缀分组教程详解》，主要内容是讲解等等，感兴趣的朋友可以收藏或者有更好的建议在评论提出，我都会认真看的！大家一起进步，一起学习！

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

终于介绍完啦！小伙伴们，这篇关于《最长公共后缀分组教程全解析》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！