查找字符串数组中最长的子字符串，并将其从数组中的所有元素中删除

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

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

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

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

Answer 1

此扩展名找到最长的最常见子字符串。 注意， "1"也包含在每个字符串中，甚至比"10"更频繁。 （仅限C＃）：

 public static class StringExtensions { public static IEnumerable GetMostCommonSubstrings(this IList 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>(); for (int i = 0; i < strings.Count; i++) { var substrings = new List(); 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[] 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

---

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

 public static string GetLongestCommonSubstring(this IList 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(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 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" 

Answer 2

试试这个:(我想常见的字符串应该在开头）：

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

Answer 3

查找长度为1的子字符串出现的最大次数。 这是一个简单的O（n ^ 2）搜索。 调用此最大出现次数K.

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

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

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