字符串算法建议查找字符串列表的所有常用前缀

Question

您建议使用什么算法来找出字符串列表中最长的公共前缀？

我可能有以下字符串:

Call Mike and schedule meeting.
Call Lisa
Call Adam and ask for quote.
Implement new class for iPhone project
Implement new class for Rails controller
Buy groceries

我想找出以下前缀:

"Call "
"Implement new class "

我将使用Objective C,因此现成的可可解决方案将是一个加号(虽然不是必须的).

Answer 1

编辑:澄清问题:

1. 排序字符串
2. 找到每个相邻对的最长公共前缀
3. 对公共前缀进行排序和重复数据删除,然后删除任何另一个的严格前缀.

实际上,步骤(3)只要求你删除任何另一个的欺骗/前缀,你可以用trie或其他任何东西而不是排序.事实上,使用适当注释的trie可以更快地完成整个事情 - 如果你在每个节点都包含一个"计数",那么你正在精确地寻找计数为2+的节点,那些没有子节点的节点数量为2+.

但是排序是内置的,一旦你排序,你可以通过查看相邻项来检测前缀,所以它可能会减少工作量.

[原始答案:

只需一次性操作,找到所有字符串之间最长的公共前缀？

我可能会根据前缀的长度来做.在伪代码中,假设以空字符结尾的字符串:

prefixlen = strlen(first_string);
foreach string in the list {
    for (i = 0; i < prefixlen; ++i) {
        if (string[i] != first_string[i]) {
            prefixlen = i;
            break;
        }
    }
    if (prefixlen == 0) break;
}

common_prefix = substring(firststring, 0, prefixlen);

]

Answer 2

这取决于您愿意考虑什么前缀。

我认为通用的答案是创建一个 Trie （可能是后缀树），将所有字符串存储到 n 叉树中。请参阅http://en.wikipedia.org/wiki/Trie

根据“前缀”的标准（例如，n 个字符），您可以选择n具有多个子节点的所有等级节点。

您将获得重复前缀的列表。