如何解析字符串数组中的子串并筛选出唯一名称？

我有一个存储名称的字符串数组，伪代码示例如下：

string nameArray[7]
nameArray[0] = "JohnJacob"
nameArray[1] = "George"
nameArray[2] = "JacobBill"
nameArray[3] = "GeorgeBill"
nameArray[4] = "PatZach"
nameArray[5] = "BobJacob"
nameArray[6] = "MichaelScottChristine"

希望处理后，数组中不存在重复出现的名称（即使作为子串出现也不行）。允许两个名称连在一起，只要这两个子串都未在数组其他元素中出现即可。一种可能的处理结果如下：

nameArrayUpdated[0] = "John"
nameArrayUpdated[1] = "Jacob"
nameArrayUpdated[2] = "George"
nameArrayUpdated[3] = "Bill"
nameArrayUpdated[4] = "PatZach"
nameArrayUpdated[5] = "Bob"
nameArrayUpdated[6] = "MichaelScottChristine"

我的初始思路是遍历数组，检查某个元素是否是另一个元素的子串，若存在则移除该子串，伪代码如下：

for (i = 0; i < arrLength; i++)
{
   str tmp = nameArray[i];
   for (j = 0; j < arrLength; j++)
   {
      if (i != j)
      {
         if (nameArray[j].ContainsSubstring(tmp) == true)
            nameArray[j].RemoveSubstring(tmp)
      }

   }
}

但该方法存在诸多问题：

• 需要未知次数的数组遍历，例如"JohnJacob"无法在第一次遍历中拆分，需第二次遍历才能处理；
• 像"JacobBill"和"BobJacob"这类字符串会被视为独立的唯一元素，但实际上两者都包含"Jacob"这个子串。

请问是否有可行的方法来拆分这些名称？

核心思路 #

先利用名称的格式特征（首字母大写）提取所有候选子串，统计子串的出现频率，优先保留高频子串并拆分包含它们的复合字符串，最后校验并确保所有元素无重复子串。

具体步骤 #

1. 提取候选子串
   遍历数组中的每个字符串，按大写字母分割成候选子串——比如"JohnJacob"拆成["John", "Jacob"]，"JacobBill"拆成["Jacob", "Bill"]。这是基于名称的常见格式，最直接的拆分方式。

2. 统计子串频率
   用哈希表统计所有候选子串的出现次数，比如：

   • "Jacob"出现在3个元素中，频率为3；
   • "George"、"Bill"各出现2次，频率为2；
   • "John"、"Bob"、"Pat"、"Zach"等仅出现1次。

3. 高频优先拆分复合串
   按频率从高到低处理子串：

   • 先处理高频子串（如"Jacob"、"George"、"Bill"），将所有包含这些子串的复合字符串拆分为独立子串，替换原数组中的对应元素；
   • 对于频率为1的子串，若其未被其他元素包含，也没有包含其他元素，则保留原复合形式（比如"PatZach"的两个子串都只出现一次，且未在其他元素中出现，所以保留；"MichaelScottChristine"的所有子串均唯一，故保留原串）。

4. 双向校验去重
   处理完成后，遍历数组进行双向检查：确保任意两个元素之间，不存在一个是另一个的子串的情况。如果发现遗漏的重复，重复上述拆分步骤。

伪代码示例 #

// 步骤1：提取候选子串并统计频率
dict freqMap
list allCandidates

for each str in nameArray:
    // 按大写字母分割字符串
    splits = splitByUppercase(str)
    allCandidates.addAll(splits)
    for each split in splits:
        freqMap[split] = freqMap.getOrDefault(split, 0) + 1

// 步骤2：按频率从高到低排序子串
sortedSubstrings = sort freqMap keys by value descending

// 步骤3：拆分复合字符串，构建初始更新数组
list updatedArray

for each str in nameArray:
    splits = splitByUppercase(str)
    // 判断是否需要拆分：拆分后的子串是否有高频项
    hasHighFreq = false
    for s in splits:
        if freqMap[s] > 1:
            hasHighFreq = true
            break
    if hasHighFreq:
        updatedArray.addAll(splits)
    else:
        updatedArray.add(str)

// 步骤4：双向校验，移除重复子串
set seen = empty set
list finalArray

for item in updatedArray:
    isDuplicate = false
    for existing in seen:
        if item.contains(existing) or existing.contains(item):
            isDuplicate = true
            break
    if not isDuplicate:
        finalArray.add(item)
        seen.add(item)

关键提示 #

• 如果数组中存在非首字母大写的名称，需要额外的分词逻辑（比如字典匹配）来拆分；
• 频率相同的子串，可按长度或首次出现顺序优先处理；
• 最终校验必须双向检查，避免遗漏“短串是长串子串”的情况。

内容的提问来源于stack exchange，提问作者nightmare637