时间：2019-03-17 标签：c#longestcommonwordssample

Question

我正在寻找最长的常用词 C# 实现。我遇到的大多数样本都是逐个字符地进行比较。

换句话说，

string1 = access
string2 = advised 

是否应该从函数的

任何示例代码中返回 null 输出？

Answer 1

我认为这个问题通常被称为最长公共子串问题。维基百科文章包含伪代码，并且可以在 Web 上找到 C# 实现。

Answer 2

如果您所说的单词指的是这些字母，并通过标点符号与其他字母分开，请尝试以下操作：

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

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

Answer 3

将计算字符数组 LCS 的算法转变为计算其他任何数组（例如单词数组）的算法通常非常简单。你尝试过吗？

如果您需要一些提示，这里是我几年前写的一篇文章，介绍如何在 JScript 中的单词数组上实现最长公共子序列。您应该能够毫无困难地使其适应 C#。

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

Answer 4

查找字符串中的差异称为最长公共子序列问题。以下是用 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< /a>.