C最长常用词示例

如果你所说的这些字母的意思是,与其他字母分开,用双关语,试着这样做:

private String longestCommonWord(String s1, String s2)
    {
        String[] seperators = new String[] { " ", ",", ".", "!", "?", ";" };
        var result = from w1 in s1.Split(seperators, StringSplitOptions.RemoveEmptyEntries)
                     where (from w2 in s2.Split(seperators, StringSplitOptions.RemoveEmptyEntries)
                            where w2 == w1
                            select w2).Count() > 0
                     orderby w1.Length descending
                     select w1;
        if (result.Count() > 0)
        {
            return result.First();
        }
        else
        {
            return null;
        }
    }

这可能不是最优雅的方式,但它对我很有用。=)

我认为这个问题通常被称为 Longest common substring problem . 维基百科的文章包含伪代码,C实现可以在网络上找到。

把计算字符数组lcs的算法转换成可以处理其他任何事情的算法——比如说,一个单词数组——通常非常简单。你试过了吗?

如果您需要一些提示,下面是我几年前写的一篇文章,关于如何在JScript中的单词数组上实现最长的公共子序列。你应该能够在不太困难的情况下使它适应C。

http://blogs.msdn.com/ericlippert/archive/2004/07/21/189974.aspx

查找字符串中的差异被称为最长的常见子序列问题。以下是用C编写的LCS问题的通用解决方案:

static int[,] GetLCSDifferenceMatrix<T>(
    Collection<T> baseline,
    Collection<T> revision)
{
    int[,] matrix = new int[baseline.Count + 1, revision.Count + 1];

    for (int baselineIndex = 0; baselineIndex < baseline.Count; baselineIndex++)
    {
        for (int revisionIndex = 0; revisionIndex < revision.Count; revisionIndex++)
        {
            if (baseline[baselineIndex].Equals(revision[revisionIndex]))
            {
                matrix[baselineIndex + 1, revisionIndex + 1] =
                    matrix[baselineIndex, revisionIndex] + 1;
            }
            else
            {
                int possibilityOne = matrix[baselineIndex + 1, revisionIndex];
                int possibilityTwo = matrix[baselineIndex, revisionIndex + 1];

                matrix[baselineIndex + 1, revisionIndex + 1] =
                    Math.Max(possibilityOne, possibilityTwo);
            }
        }
    }

    return matrix;
}

这段代码给出了一个“差分”矩阵,然后可以用它来构造两个输入的差分。有关单元测试和示例用法,请参见 http://sethflowers.com/2012/01/18/basic-diff-with-a-generic-solution-to-the-longest-common-subsequence-problem.html .