1

我正在寻找一种巧妙的方法来在字符串列表中找到字符串的最大公共部分。我想要一种从看起来像的列表中走出来的方法

{"1 Some Street, Some Town, XYZ" ,
"2 Some Street, Some Town, ABC" ,
"3 Some Street, Some Town, XYZ" ,
"4 Some Street, Some Town, ABC" }

返回单个字符串"Some Street, Some Town, "。我不知道字符串的公共部分是在输入列表中字符串的开头、结尾还是中间，我认为应该有一种巧妙的方法来做到这一点，但我想不出其中。

4

1 回答 1

2

改编自 gloomy.penguin 的评论，使用http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring。

static void Main(string[] args)
{
    var values = new List<string>
    {"1 Some Street, Some Town, XYZ" ,
    "2 Some Street, Some Town, ABC" ,
    "3 Some Street, Some Town, XYZ" ,
    "4 Some Street, Some Town, ABC" };

    Console.WriteLine(LongestCommonSubstring(values));

    Console.ReadLine();
}

public static string LongestCommonSubstring(IList<string> values)
{
    string result = string.Empty;

    for (int i = 0; i < values.Count - 1; i++)
    {
        for (int j = i + 1; j < values.Count; j++)
        {
            string tmp;
            if (LongestCommonSubstring(values[i], values[j], out tmp) > result.Length)
            {
                result = tmp;
            }
        }
    }

    return result;
}

// Source: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring
public static int LongestCommonSubstring(string str1, string str2, out string sequence)
{
    sequence = string.Empty;
    if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
        return 0;

    int[,] num = new int[str1.Length, str2.Length];
    int maxlen = 0;
    int lastSubsBegin = 0;
    StringBuilder sequenceBuilder = new StringBuilder();

    for (int i = 0; i < str1.Length; i++)
    {
        for (int j = 0; j < str2.Length; j++)
        {
            if (str1[i] != str2[j])
                num[i, j] = 0;
            else
            {
                if ((i == 0) || (j == 0))
                    num[i, j] = 1;
                else
                    num[i, j] = 1 + num[i - 1, j - 1];

                if (num[i, j] > maxlen)
                {
                    maxlen = num[i, j];
                    int thisSubsBegin = i - num[i, j] + 1;
                    if (lastSubsBegin == thisSubsBegin)
                    {//if the current LCS is the same as the last time this block ran
                        sequenceBuilder.Append(str1[i]);
                    }
                    else //this block resets the string builder if a different LCS is found
                    {
                        lastSubsBegin = thisSubsBegin;
                        sequenceBuilder.Length = 0; //clear it
                        sequenceBuilder.Append(str1.Substring(lastSubsBegin, (i + 1) - lastSubsBegin));
                    }
                }
            }
        }
    }
    sequence = sequenceBuilder.ToString();
    return maxlen;
}

注意：这假设在出现平局时先到先得。

于 2012-11-14T18:23:12.790 回答