0

例如，我有这个数组（大小是可变的）：

x = ["10111", "10122", "10250", "10113"]

我需要找到最长的字符串，它是每个数组元素的子字符串（在这种情况下为“10”）（它不必是字符串的前缀）。我必须从所有字符串中删除它。此示例的输出将是：

x=["111","222","250","113"] //common value = "10"
4

3 回答 3

6

此扩展查找最长最常见的子字符串。请注意，"1"每个字符串中也包含"10". （仅限 C#）：

public static class StringExtensions
{
    public static IEnumerable<string> GetMostCommonSubstrings(this IList<string> strings)
    {
        if (strings == null)
            throw new ArgumentNullException("strings");
        if (!strings.Any() || strings.Any(s => string.IsNullOrEmpty(s)))
            throw new ArgumentException("None string must be empty", "strings");

        var allSubstrings = new List<List<string>>();
        for (int i = 0; i < strings.Count; i++)
        {
            var substrings = new List<string>();
            string str = strings[i];
            for (int c = 0; c < str.Length - 1; c++)
            {
                for (int cc = 1; c + cc <= str.Length; cc++)
                {
                    string substr = str.Substring(c, cc);
                    if (allSubstrings.Count < 1 || allSubstrings.Last().Contains(substr))
                        substrings.Add(substr);
                }
            }
            allSubstrings.Add(substrings);
        }
        if (allSubstrings.Last().Any())
        {
            var mostCommon = allSubstrings.Last()
                .GroupBy(str => str)
                .OrderByDescending(g => g.Key.Length)
                .ThenByDescending(g => g.Count())
                .Select(g => g.Key);
            return mostCommon;
        }
        return Enumerable.Empty<string>();
    }
}

现在很容易：

string[] x = new[] { "10111", "10122", "10250", "10113" };
string mostCommonSubstring = x.GetMostCommonSubstrings().FirstOrDefault();
if (mostCommonSubstring != null)
{
    for (int i = 0; i < x.Length; i++)
        x[i] = x[i].Replace(mostCommonSubstring, "");
}
Console.Write(string.Join(", ", x));

输出：

111, 122, 250, 113

DEMO

编辑：如果您只想找到最长的公共子字符串而不考虑出现频率，您可以使用以下优化方法（O（n）操作）HashSet<string>：

public static string GetLongestCommonSubstring(this IList<string> strings)
{
    if (strings == null)
        throw new ArgumentNullException("strings");
    if (!strings.Any() || strings.Any(s => string.IsNullOrEmpty(s)))
        throw new ArgumentException("None string must be empty", "strings");

    var commonSubstrings = new HashSet<string>(strings[0].GetSubstrings());
    foreach (string str in strings.Skip(1))
    {
        commonSubstrings.IntersectWith(str.GetSubstrings());
        if (commonSubstrings.Count == 0)
            return null;
    }
    return commonSubstrings.OrderByDescending(s => s.Length).First();
}

public static IEnumerable<string> GetSubstrings(this string str)
{
    if (string.IsNullOrEmpty(str))
        throw new ArgumentException("str must not be null or empty", "str");

    for (int c = 0; c < str.Length - 1; c++)
    {
        for (int cc = 1; c + cc <= str.Length; cc++)
        {
            yield return str.Substring(c, cc);
        }
    }
}

以这种方式使用它：

string[] x = new[] { "101133110", "101233210", "102533010", "101331310" };
string longestCommon = x.GetLongestCommonSubstring();  // "10"
于 2013-09-23T07:31:53.350 回答
1

求长度为 1 的子串出现的最大次数。这是一个简单的 O(n^2) 搜索。将此最大出现次数称为 K。

在您的示例中，这是“1”、“0”和 K=5。

现在您知道所有长度为 2 的子字符串不能出现在超过 K 个输入字符串中。此外，任何出现 K 次的子串必须由出现 K 次的长度为 1 的子串组成。在长度为 1 的子串中搜索存在 K 次的长度为 2 的子串，这又是一个简单的 O(n^2) 搜索。

重复更长的长度，直到 K 个输入中不再存在子字符串。

于 2013-09-23T09:25:56.600 回答
1

试试这个：（我想公共字符串应该在开头）：

string[] x = {"10111","10222","10250","10113"};
string common = x[0];
foreach(var i in x){
  while(!i.StartsWith(common)){
    common = common.Substring(0,common.Length-1);
    if(common == "") break;
  }
}
x = x.Select(a=>a.Substring(common.Length)).ToArray();
于 2013-09-23T07:12:29.017 回答