查找多个公共前缀字符串

Question

我有一个字符串列表，其中一个或多个子集的字符串有一个共同的开头部分。我想要一个函数，它可以接收这个原始字符串列表，并返回所有共同的开头部分。在我的具体情况下，我还知道每个共同的前缀必须以一个特定的分隔符结束。下面是我所说的输入数据的一个例子（忽略任何颜色高亮）：

Population of metro area / Portland
Population of city / Portland
Population of metro area / San Francisco
Population of city / San Francisco
Population of metro area / Seattle
Population of city / Seattle

在这里，分隔符是 /，共同的开头部分是 Population of metro area 和 Population of city。也许分隔符最终并不重要，但我提到它是为了强调我不想只得到一个结果，也就是普遍的共同开头部分 Population of；我也不想要共同的子字符串 Population of metro area / S 和 Population of city / S。

这个算法的最终用途是根据它们的共同前缀对字符串进行分组。例如，上面的列表可以重新组织成一个层次结构，从而消除冗余信息，如下所示：

Population of metro area
    Portland
    San Francisco
    Seattle
Population of city
    Portland
    San Francisco
    Seattle

我使用的是Python，但任何语言的伪代码都可以。

编辑：正如Tom Anderson所提到的，原始问题可以很容易地简化为仅仅拆分字符串并使用哈希表按前缀分组。我最初认为这个问题可能更复杂，因为在实际操作中我有时会遇到带有嵌入分隔符的前缀，但我意识到这也可以通过简单地进行一次右侧拆分来解决，只拆分一次。

Answer 1

使用 csv.reader 和 itertools.groupby，把 '/' 当作分隔符，并根据第一列进行分组：

for key, group in groupby(sorted(reader(inp, delimiter='/')), key=lambda x: x[0]):
    print key
    for line in group:
        print "\t", line[1]

Answer 2

d = collections.defaultdict(list)

for place, name in ((i.strip() for i in line.split('/'))
                    for line in text.splitlines()):
    d[place].append(name)

所以 d 将会是一个字典，像这样：

{'Population of city':
       ['Portland',
        'San Francisco',
        'Seattle'],
 'Population of metro area':
       ['Portland',
        'San Francisco',
        'Seattle']}

---

如果你确定你的文本周围没有多余的空格，可以用 line.split(' / ') 来替代 (i.strip() for i in line.split('/')。

Answer 3

这不就是在遍历字符串吗？把它们根据分隔符拆分开，然后把后半部分按前半部分分组吗？就像这样：

def groupByPrefix(strings):
    stringsByPrefix = {}
    for string in strings:
            prefix, suffix = map(str.strip, string.split("/", 1))
            group = stringsByPrefix.setdefault(prefix, [])
            group.append(suffix)
    return stringsByPrefix

一般来说，如果你想找字符串的前缀，解决办法是把字符串放进一个叫做字典树的结构里。任何有多个子节点的分支节点就是一个最大的公共前缀。不过你的需求比这个要更具体一些。