prefijo común de cadenas

Question

que estoy teniendo 4 cuerdas:

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

Quiero encontrar el prefijo común para esas cadenas, es decir "h:/a". ¿Cómo encontrar eso?

Normalmente dividiría la cadena con el delimitador '/' y lo pondría en otra lista, y así sucesivamente.
¿Hay alguna forma mejor de hacerlo?

Answer 1

Este es el problema longest common substring (aunque es un caso ligeramente especializado ya que parece que solo le importa el prefijo). No existe una implementación de la biblioteca del algoritmo en la plataforma .NET a la que pueda llamar directamente, pero el artículo aquí enlazado está repleto de pasos sobre cómo lo haría usted mismo.

Answer 2

Simplemente recorra los caracteres de la secuencia más corta y compare cada carácter con el carácter en la misma posición en las otras cadenas. Mientras todos los partidos continúan. Tan pronto como no coincida, la cadena hasta la posición actual -1 es la respuesta.

Algo así como (pseudo código)

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

código de trabajo basado en la solución de Sam Holder (nota que da h:/a/No h:/a como la subcadena inicial común más larga en la pregunta):

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

Quería un prefijo de cadena común, excepto que quería incluir cualquier carácter (como /) y no quería algo que funcionara/fuera de fantasía solo algo que pueda leer con las pruebas. Así que tengo esto: 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

Aquí es una implementación personalizada del algoritmo trie en C# (http://en.wikipedia.org/wiki/Trie). Se utiliza para realizar una cadena indexada a través de prefijos. Esta clase tiene O (1) escribe y lee para nodos hoja. Para las búsquedas de prefijos, el rendimiento es O (log n), sin embargo, el recuento de resultados para el prefijo es 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>(); 
     } 
    } 
} 

Aquí es el código de ejemplo, la unidad de pruebas & para el uso de esta clase.

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

¿Alguna sugerencia sobre cómo mejorar esta clase son bienvenidos :)

Answer 7

Mi enfoque sería, tomar la primera cadena. Obtenga letra por letra, mientras que todas las demás cadenas tienen la misma letra en la misma posición de índice y se detienen si no coinciden. Elimina el último carácter si es un separador.

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

Necesitaba buscar el prefijo común más largo en cadenas diferentes.Se me ocurrió:

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

Si hay más de un prefijo con la misma longitud, de manera arbitraria devuelve la primera que se encuentre. También es sensible a mayúsculas y minúsculas. ¡Ambos puntos pueden ser abordados por el lector!

Answer 9

Escribí esta extensión ICollection para encontrar el Uri base común más largo de una colección de direcciones web.

Como solo comprueba la colección de cadenas en cada barra, será un poco más rápido que una rutina de prefijo genérico (¡sin contar mi algoritmo ineficiente!). Es detallado, pero fácil de seguir ... mi tipo de código favorito ;-)

Ignora 'http: //' y 'https: //', así como el estuche.

/// <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 solución corta de LINQy mía.

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