Trova prefisso comune di stringhe

Question

che sto avendo 4 stringhe:

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

Voglio trovare il prefisso comune per quelle stringhe, vale a dire "h:/a". Come trovarlo?

Solitamente mi piacerebbe dividere la stringa con il delimitatore '/' e inserirla in un'altra lista, e così via.
C'è un modo migliore per farlo?

Answer 1

Questo è il problema longest common substring (anche se si tratta di un caso leggermente specializzato poiché sembra interessarsi solo del prefisso). Non esiste implementazione della libreria dell'algoritmo nella piattaforma .NET che è possibile chiamare direttamente, ma l'articolo collegato qui è pieno zeppo di passaggi su come lo faresti tu stesso.

Answer 2

Basta fare un giro attorno ai caratteri della stringa più breve e confrontare ogni carattere con il personaggio nella stessa posizione nelle altre stringhe. Mentre tutti corrispondono continuano ad andare avanti. Non appena uno non corrisponde, la stringa fino alla posizione corrente -1 è la risposta.

Qualcosa di simile (pseudo codice)

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

con

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

codice di lavoro basato sulla soluzione del titolare del Sam (nota dà h:/a/non h:/a come la più lunga sottostringa iniziale comune nella domanda):

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

Volevo un prefisso di stringa comune, tranne che volevo includere qualsiasi carattere (come /) e non volevo qualcosa di performante/di fantasia solo qualcosa che posso leggere con i test. Così ho questo: 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

Ecco un'implementazione personalizzata dell'algoritmo trie in C# (http://en.wikipedia.org/wiki/Trie). Viene utilizzato per eseguire una stringa indicizzata tramite prefissi. Questa classe ha O (1) scrivere e leggere per i nodi foglia. Per le ricerche prefisso, la performance è O (log n), tuttavia il conteggio dei risultati per il prefisso è 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>(); 
     } 
    } 
} 

Ecco il codice di esempio unità di prova & per come utilizzare questa classe.

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

Qualche suggerimento su come migliorare questa classe sono i benvenuti :)

Answer 7

Il mio approccio sarebbe, prendere la prima stringa. Ricevi lettere per lettera mentre tutte le altre stringhe hanno la stessa lettera nella stessa posizione di indice e si fermano se non c'è corrispondenza. Rimuovi l'ultimo carattere se si tratta di un separatore.

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

Avevo bisogno di cercare il prefisso comune più lungo in stringhe dissimili.Mi si avvicinò con:

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

Se v'è più di un prefisso con la stessa lunghezza, restituisce arbitrariamente il primo trovato. Inoltre è case-sensitive. Entrambi questi punti possono essere indirizzati dal lettore!

Answer 9

Ho scritto questa estensione ICollection per trovare la più lunga base comune Uri da una raccolta di indirizzi Web.

Come si controlla solo la raccolta di stringhe a ogni barra sarà un po 'più veloce che una routine di prefisso generico (Senza contare il mio algoritmo inefficiente!). È prolisso, ma facile da seguire ... il mio tipo di codice preferito ;-)

Ignora 'http: //' e 'https: //', oltre al caso.

/// <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

Una piccola soluzione LINQy.

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