Tìm tiền tố chung của chuỗi

Question

Tôi gặp 4 dây:

"h:/a/b/c" 
"h:/a/b/d" 
"h:/a/b/e" 
"h:/a/c" 

Tôi muốn tìm tiền tố phổ biến đối với những chuỗi, ví dụ: "h:/a". Làm cách nào để tìm?

Thông thường tôi sẽ chia chuỗi có dấu phân cách '/' và đặt nó vào danh sách khác, v.v.
Có cách nào tốt hơn để làm điều đó không?

Answer 1

Đây là sự cố longest common substring (mặc dù đây là trường hợp hơi đặc biệt vì bạn dường như chỉ quan tâm đến tiền tố). Không có thư viện thực hiện thuật toán trong nền tảng .NET mà bạn có thể gọi trực tiếp, nhưng bài viết được liên kết ở đây là đầy đủ các bước về cách bạn tự làm.

Answer 2

Chỉ vòng lặp các ký tự của chuỗi ngắn nhất và so sánh từng ký tự với ký tự ở cùng vị trí trong các chuỗi khác. Trong khi họ tất cả các trận đấu tiếp tục đi. Ngay sau khi một không khớp thì chuỗi đến vị trí hiện tại -1 là câu trả lời.

Giống như (pseudo code)

int count=0; 
foreach(char c in shortestString) 
{ 
    foreach(string s in otherStrings) 
    { 
     if (s[count]!=c) 
     { 
      return shortestString.SubString(0,count-1); //need to check count is not 0 
     } 
    } 
    count+=1; 
} 
return shortestString; 

Answer 3

string[] xs = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/c" }; 

string x = string.Join("/", xs.Select(s => s.Split('/').AsEnumerable()) 
           .Transpose() 
           .TakeWhile(s => s.All(d => d == s.First())) 
           .Select(s => s.First())); 

với

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source) 
{ 
    var enumerators = source.Select(e => e.GetEnumerator()).ToArray(); 
    try 
    { 
     while (enumerators.All(e => e.MoveNext())) 
     { 
      yield return enumerators.Select(e => e.Current).ToArray(); 
     } 
    } 
    finally 
    { 
     Array.ForEach(enumerators, e => e.Dispose()); 
    } 
} 

Answer 4

đang làm việc dựa trên giải pháp Sam Chủ nhân (lưu ý nó mang lại cho h:/a/không h:/A như chuỗi con ban đầu chung dài nhất trong câu hỏi):

using System; 

namespace CommonPrefix 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      Console.WriteLine(CommonPrefix(new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/c" })); // "h:/a/" 
      Console.WriteLine(CommonPrefix(new[] { "abc", "abc" })); // "abc" 
      Console.WriteLine(CommonPrefix(new[] { "abc" })); // "abc" 
      Console.WriteLine(CommonPrefix(new string[] { })); // "" 
      Console.WriteLine(CommonPrefix(new[] { "a", "abc" })); // "a" 
      Console.WriteLine(CommonPrefix(new[] { "abc", "a" })); // "a" 

      Console.ReadKey(); 
     } 

     private static string CommonPrefix(string[] ss) 
     { 
      if (ss.Length == 0) 
      { 
       return ""; 
      } 

      if (ss.Length == 1) 
      { 
       return ss[0]; 
      } 

      int prefixLength = 0; 

      foreach (char c in ss[0]) 
      { 
       foreach (string s in ss) 
       { 
        if (s.Length <= prefixLength || s[prefixLength] != c) 
        { 
         return ss[0].Substring(0, prefixLength); 
        } 
       } 
       prefixLength++; 
      } 

      return ss[0]; // all strings identical up to length of ss[0] 
     } 
    } 
} 

Answer 5

Tôi muốn có một tiền tố chuỗi chung, ngoại trừ tôi muốn bao gồm bất kỳ ký tự nào (như /) và tôi không muốn một cái gì đó biểu diễn/ưa thích chỉ là một cái gì đó tôi có thể đọc với các bài kiểm tra. Vì vậy, tôi có điều này: https://github.com/fschwiet/DreamNJasmine/commit/ad802611ceacc673f2d03c30f7c8199f552b586f

public class CommonStringPrefix 
{ 
    public static string Of(IEnumerable<string> strings) 
    { 
     var commonPrefix = strings.FirstOrDefault() ?? ""; 

     foreach(var s in strings) 
     { 
      var potentialMatchLength = Math.Min(s.Length, commonPrefix.Length); 

      if (potentialMatchLength < commonPrefix.Length) 
       commonPrefix = commonPrefix.Substring(0, potentialMatchLength); 

      for(var i = 0; i < potentialMatchLength; i++) 
      { 
       if (s[i] != commonPrefix[i]) 
       { 
        commonPrefix = commonPrefix.Substring(0, i); 
        break; 
       } 
      } 
     } 

     return commonPrefix; 
    } 
} 

Answer 6

Đây là một thực hiện tùy chỉnh của thuật toán Trie trong C# (http://en.wikipedia.org/wiki/Trie). Nó được sử dụng để thực hiện một chuỗi được lập chỉ mục thông qua các tiền tố. Lớp này có O (1) viết và đọc cho các nút lá. Đối với các tìm kiếm tiền tố, hiệu suất là O (log n), tuy nhiên số lượng kết quả cho tiền tố là O (1).

using System; 
using System.Collections; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

public class StringIndex 
{ 
    private Dictionary<char, Item> _rootChars; 

    public StringIndex() 
    { 
     _rootChars = new Dictionary<char, Item>(); 
    } 

    public void Add(string value, string data) 
    { 
     int level = 0; 
     Dictionary<char, Item> currentChars = _rootChars; 
     Item currentItem = null; 

     foreach (char c in value) 
     { 
      if (currentChars.ContainsKey(c)) 
      { 
       currentItem = currentChars[c]; 
      } 
      else 
      { 
       currentItem = new Item() { Level = level, Letter = c }; 
       currentChars.Add(c, currentItem);     
      } 

      currentChars = currentItem.Items; 

      level++; 
     } 

     if (!currentItem.Values.Contains(data)) 
     { 
      currentItem.Values.Add(data); 
      IncrementCount(value); 
     } 
    } 

    private void IncrementCount(string value) 
    { 
     Dictionary<char, Item> currentChars = _rootChars; 
     Item currentItem = null; 

     foreach (char c in value) 
     { 
      currentItem = currentChars[c]; 
      currentItem.Total++; 
      currentChars = currentItem.Items; 
     } 
    } 

    public void Remove(string value, string data) 
    { 
     Dictionary<char, Item> currentChars = _rootChars; 
     Dictionary<char, Item> parentChars = null; 
     Item currentItem = null; 

     foreach (char c in value) 
     { 
      if (currentChars.ContainsKey(c)) 
      { 
       currentItem = currentChars[c]; 
       parentChars = currentChars; 
       currentChars = currentItem.Items; 
      } 
      else 
      { 
       return; // no matches found 
      } 
     } 

     if (currentItem.Values.Contains(data)) 
     { 
      currentItem.Values.Remove(data); 
      DecrementCount(value); 
      if (currentItem.Total == 0) 
      { 
       parentChars.Remove(currentItem.Letter); 
      } 
     } 
    } 

    private void DecrementCount(string value) 
    { 
     Dictionary<char, Item> currentChars = _rootChars; 
     Item currentItem = null; 

     foreach (char c in value) 
     { 
      currentItem = currentChars[c]; 
      currentItem.Total--; 
      currentChars = currentItem.Items; 
     } 
    } 

    public void Clear() 
    { 
     _rootChars.Clear(); 
    } 

    public int GetValuesByPrefixCount(string prefix) 
    { 
     int valuescount = 0; 

     int level = 0; 
     Dictionary<char, Item> currentChars = _rootChars; 
     Item currentItem = null; 

     foreach (char c in prefix) 
     { 
      if (currentChars.ContainsKey(c)) 
      { 
       currentItem = currentChars[c]; 
       currentChars = currentItem.Items; 
      } 
      else 
      { 
       return valuescount; // no matches found 
      } 
      level++; 
     } 

     valuescount = currentItem.Total; 

     return valuescount; 
    } 

    public HashSet<string> GetValuesByPrefixFlattened(string prefix) 
    { 
     var results = GetValuesByPrefix(prefix); 
     return new HashSet<string>(results.SelectMany(x => x)); 
    } 

    public List<HashSet<string>> GetValuesByPrefix(string prefix) 
    { 
     var values = new List<HashSet<string>>(); 

     int level = 0; 
     Dictionary<char, Item> currentChars = _rootChars; 
     Item currentItem = null; 

     foreach (char c in prefix) 
     { 
      if (currentChars.ContainsKey(c)) 
      { 
       currentItem = currentChars[c]; 
       currentChars = currentItem.Items; 
      } 
      else 
      { 
       return values; // no matches found 
      } 
      level++; 
     } 

     ExtractValues(values, currentItem); 

     return values; 
    } 

    public void ExtractValues(List<HashSet<string>> values, Item item) 
    { 
     foreach (Item subitem in item.Items.Values) 
     { 
      ExtractValues(values, subitem); 
     } 

     values.Add(item.Values); 
    } 

    public class Item 
    { 
     public int Level { get; set; } 
     public char Letter { get; set; } 
     public int Total { get; set; } 
     public HashSet<string> Values { get; set; } 
     public Dictionary<char, Item> Items { get; set; } 

     public Item() 
     { 
      Values = new HashSet<string>(); 
      Items = new Dictionary<char, Item>(); 
     } 
    } 
} 

Đây là mã thử nghiệm đơn vị & ví dụ về cách sử dụng lớp này.

using System; 
using Microsoft.VisualStudio.TestTools.UnitTesting; 

    [TestClass] 
    public class StringIndexTest 
    { 
     [TestMethod] 
     public void AddAndSearchValues() 
     { 

      var si = new StringIndex(); 

      si.Add("abcdef", "1"); 
      si.Add("abcdeff", "2"); 
      si.Add("abcdeffg", "3"); 
      si.Add("bcdef", "4"); 
      si.Add("bcdefg", "5"); 
      si.Add("cdefg", "6"); 
      si.Add("cdefgh", "7"); 

      var output = si.GetValuesByPrefixFlattened("abc"); 

      Assert.IsTrue(output.Contains("1") && output.Contains("2") && output.Contains("3")); 
     } 

     [TestMethod] 
     public void RemoveAndSearch() 
     { 

      var si = new StringIndex(); 

      si.Add("abcdef", "1"); 
      si.Add("abcdeff", "2"); 
      si.Add("abcdeffg", "3"); 
      si.Add("bcdef", "4"); 
      si.Add("bcdefg", "5"); 
      si.Add("cdefg", "6"); 
      si.Add("cdefgh", "7"); 

      si.Remove("abcdef", "1"); 

      var output = si.GetValuesByPrefixFlattened("abc"); 

      Assert.IsTrue(!output.Contains("1") && output.Contains("2") && output.Contains("3")); 
     } 

     [TestMethod] 
     public void Clear() 
     { 

      var si = new StringIndex(); 

      si.Add("abcdef", "1"); 
      si.Add("abcdeff", "2"); 
      si.Add("abcdeffg", "3"); 
      si.Add("bcdef", "4"); 
      si.Add("bcdefg", "5"); 
      si.Add("cdefg", "6"); 
      si.Add("cdefgh", "7"); 

      si.Clear(); 
      var output = si.GetValuesByPrefix("abc"); 

      Assert.IsTrue(output.Count == 0); 
     } 

     [TestMethod] 
     public void AddAndSearchValuesCount() 
     { 

      var si = new StringIndex(); 

      si.Add("abcdef", "1"); 
      si.Add("abcdeff", "2"); 
      si.Add("abcdeffg", "3"); 
      si.Add("bcdef", "4"); 
      si.Add("bcdefg", "5"); 
      si.Add("cdefg", "6"); 
      si.Add("cdefgh", "7"); 

      si.Remove("cdefgh", "7"); 

      var output1 = si.GetValuesByPrefixCount("abc"); 
      var output2 = si.GetValuesByPrefixCount("b"); 
      var output3 = si.GetValuesByPrefixCount("bc"); 
      var output4 = si.GetValuesByPrefixCount("ca"); 

      Assert.IsTrue(output1 == 3 && output2 == 2 && output3 == 2 && output4 == 0); 
     } 
    } 

Bất kỳ đề xuất về cách cải thiện lớp này được hoan nghênh :)

Answer 7

Tiếp cận của tôi sẽ là, lấy chuỗi đầu tiên. Nhận thư bằng thư trong khi tất cả chuỗi khác có cùng một chữ cái trên cùng một vị trí chỉ mục và dừng nếu không có kết quả trùng khớp. Xóa ký tự cuối cùng nếu đó là dấu tách.

var str_array = new string[]{"h:/a/b/c", 
     "h:/a/b/d", 
     "h:/a/b/e", 
     "h:/a/c"}; 
var separator = '/'; 

// get longest common prefix (optinally use ToLowerInvariant) 
var ret = str_array.Any() 
    ? str_array.First().TakeWhile((s,i) => 
     str_array.All(e => 
      Char.ToLowerInvariant(s) == Char.ToLowerInvariant(e.Skip(i).Take(1).SingleOrDefault()))) 
    : String.Empty; 

// remove last character if it's a separator (optional) 
if (ret.LastOrDefault() == separator) 
    ret = ret.Take(ret.Count() -1); 

string prefix = new String(ret.ToArray()); 

Answer 8

Tôi cần tìm kiếm tiền tố chung dài nhất trong các chuỗi không giống nhau.Tôi đã đưa ra:

private string FindCommonPrefix(List<string> list) 
{ 
    List<string> prefixes = null; 
    for (int len = 1; ; ++len) 
    { 
     var x = list.Where(s => s.Length >= len) 
        .GroupBy(c => c.Substring(0,len)) 
        .Where(grp => grp.Count() > 1) 
        .Select(grp => grp.Key) 
        .ToList(); 

     if (!x.Any()) 
     { 
      break; 
     } 
     // Copy last list 
     prefixes = new List<string>(x); 
    } 

    return prefixes == null ? string.Empty : prefixes.First(); 
} 

Nếu có nhiều tiền tố có cùng độ dài, nó tùy ý trả về giá trị đầu tiên được tìm thấy. Nó cũng phân biệt chữ hoa chữ thường. Cả hai điểm này đều có thể được đọc bởi người đọc!

Answer 9

Tôi đã viết phần mở rộng ICollection này để tìm URI cơ sở dài nhất từ ​​một tập hợp các địa chỉ web.

Vì nó chỉ kiểm tra việc thu thập chuỗi tại mỗi dấu gạch chéo, nó sẽ nhanh hơn một chút so với thường trình tiền tố chung (Không tính thuật toán không hiệu quả của tôi!). It's verbose, nhưng dễ làm theo ... loại yêu thích của tôi về mã ;-)

Bỏ qua 'http: //' và 'https: //', cũng như trường hợp.

/// <summary> 
    /// Resolves a common base Uri from a list of Uri strings. Ignores case. Includes the last slash 
    /// </summary> 
    /// <param name="collectionOfUriStrings"></param> 
    /// <returns>Common root in lowercase</returns> 
    public static string GetCommonUri(this ICollection<string> collectionOfUriStrings) 
    { 
     //Check that collection contains entries 
     if (!collectionOfUriStrings.Any()) 
      return string.Empty; 
     //Check that the first is no zero length 
     var firstUri = collectionOfUriStrings.FirstOrDefault(); 
     if(string.IsNullOrEmpty(firstUri)) 
      return string.Empty; 

     //set starting position to be passed '://' 
     int previousSlashPos = firstUri.IndexOf("://", StringComparison.OrdinalIgnoreCase) + 2; 
     int minPos = previousSlashPos + 1; //results return must have a slash after this initial position 
     int nextSlashPos = firstUri.IndexOf("/", previousSlashPos + 1, StringComparison.OrdinalIgnoreCase); 
     //check if any slashes 
     if (nextSlashPos == -1) 
      return string.Empty; 

     do 
     {    
      string common = firstUri.Substring(0, nextSlashPos + 1); 
      //check against whole collection 
      foreach (var collectionOfUriString in collectionOfUriStrings) 
      { 
       if (!collectionOfUriString.StartsWith(common, StringComparison.OrdinalIgnoreCase)) 
       { 
        //return as soon as a mismatch is found 
        return previousSlashPos > minPos ? firstUri.Substring(0, previousSlashPos + 1).ToLower() : string.Empty ; 
       } 
      } 
      previousSlashPos = nextSlashPos;     
      nextSlashPos = firstUri.IndexOf("/", previousSlashPos + 1, StringComparison.OrdinalIgnoreCase); 
     } while (nextSlashPos != -1); 

     return previousSlashPos > minPos ? firstUri.Substring(0, previousSlashPos + 1).ToLower() : string.Empty; 
    } 

Answer 10

Giải pháp LINQy ngắn của tôi.

var samples = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/e" }; 

var commonPrefix = new string(
    samples.First().Substring(0, samples.Min(s => s.Length)) 
    .TakeWhile((c, i) => samples.All(s => s[i] == c)).ToArray());