字符串算法建议，用于查找字符串列表的所有公共(public)前缀

Question

您建议使用哪种算法来找出字符串列表的最长公共(public)前缀？

我可能有这样的字符串:

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，所以现成的 cocoa 解决方案会更好(尽管不是必须的)。

Answer 1

编辑:对于澄清的问题:

1. 对字符串进行排序
2. 找到每个相邻对的最长公共(public)前缀
3. 对常见前缀进行排序和去重，然后删除任何属于另一个前缀的严格前缀。

实际上，步骤 (3) 只需要您删除任何与另一个相同的重复项/前缀，您可以使用 trie 或其他任何方式来代替排序。事实上，使用适当注释的特里树可能会更快地完成整个事情——如果你在每个节点都包含一个“计数”，那么你正在精确地寻找计数为 2+ 的节点，这些节点没有子节点计数 2+。

但是排序是内置的，排序后您可以通过查看相邻项目来检测前缀，因此可能更省力。

[原答案:

只是一次性的操作，找到所有字符串之间的最长公共(public)前缀？

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

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);

]