2010-01-15 1 views
23

che sto avendo 4 stringhe:Trova prefisso comune di 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?

+0

intendi dire che vuoi trovare stringhe comuni a tutti; o che ci sarà solo una stringa comune a tutti? –

+1

h:/è un disco? limitare l'immissione dei dati può darti una risposta migliore adatta alle tue necessità. – joetsuihk

+1

Ho chiarito la domanda su come la capisco. Si prega di annullare se questo è sbagliato. – dtb

risposta

4

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.

+0

non penso che la logica funzionerà qui ... voglio solo tracciare da prima e smettere quando viene la differenza – user251334

+0

ho dato un +1 perché la domanda originale non chiedeva un prefisso, richiedeva solo la sottostringa comune (presumibilmente dovevamo inferire se era un prefisso dai dati, ma non era quello che era chiesto). –

+2

Dato che viene cercato solo un prefisso comune, l'algoritmo di sottostringa comune più lungo generale sarebbe un terribile overkill (O (n^2) contro O (n) per solo due stringhe ...). Il problema NON è un "caso leggermente specializzato" ma molto più facile da risolvere :-). Di solito, darei -1 (per portare la risposta corretta), ma dato che la domanda è stata riformulata, lascerò semplicemente :-) ... – MartinStettner

12

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; 
+0

ma se ho un po 'di 20 stringhe .. pensi che il confronto tra il più breve con gli altri char per char sia efficace? – user251334

+2

Se hai solo 20 stringhe, non penso che tu debba preoccuparti dell'efficienza, ma non sono sicuro di cosa puoi fare di più, dato che devi controllare ogni stringa per assicurarti che siano uguali. potresti essere in grado di farlo meglio se sai se le stringhe potrebbero essere comuni per una certa quantità. –

+0

@deepasundari - Se è necessario trovare il primo carattere diverso nelle stringhe, il numero minimo di caratteri che è possibile confrontare è uguale all'inizio in ogni stringa, più uno diverso in una stringa. Quindi questo è probabilmente l'algoritmo più efficiente per trovare un prefisso comune. –

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

funzionerà solo se sono separati da "/"? –

+0

Se si rimuove il 'Split', funziona anche con i singoli caratteri. – dtb

+0

grazie, questa è una risposta più interessante della mia. –

6

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] 
     } 
    } 
} 
+1

Un punto secondario: il tuo commento sulla dichiarazione di reso in fondo al tuo codice indica "tutte le stringhe identiche". Quello non è vero. Il test eseguito da questa funzione verifica solo se la radice delle altre stringhe nell'array ss corrisponde a ss [0] fino alla lunghezza di ss [0]. Altre stringhe negli array ss potrebbero essere più lunghe di ss [0]. Tuttavia, il codice sta eseguendo correttamente il compito richiesto dal mio occhio. – JHubbard80

+0

Grazie @ JHubbard80, corretto questo. –

2

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

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 :)

1

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

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!

1

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

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

Soluzione semplice e breve e molto più facile da capire rispetto a tutti gli altri. – HimBromBeere