Finde das gemeinsame Präfix von Strings

Ich habe 4 Saiten:

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

Ich möchte das gemeinsame Präfix für diese Strings finden, zB "h:/a" . Wie finde ich das?

Normalerweise würde ich die Zeichenfolge mit dem Trennzeichen '/' teilen und sie in eine andere Liste einfügen, und so weiter.
Gibt es einen besseren Weg?

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

mit

 public static IEnumerable> Transpose( this IEnumerable> 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()); } } 

Eine kurze LINQy-Lösung von mir.

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

Runden Sie einfach die Zeichen der kürzesten Zeichenfolge um und vergleichen Sie jedes Zeichen mit dem Zeichen an der gleichen Position in den anderen Zeichenfolgen. Während sie alle übereinstimmen, weitermachen. Sobald man nicht übereinstimmt, ist der String bis zur aktuellen Position -1 die Antwort.

Etwas wie (Pseudocode)

 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; 

Arbeitscode basierend auf Sam Holders Lösung (beachten Sie, dass h: / a / nicht h: / a die längste gemeinsame erste Teilzeichenfolge in der Frage ist):

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

Dies ist das längste gemeinsame Teilstring- Problem (obwohl es ein leicht spezialisierter Fall ist, da Sie anscheinend nur auf das Präfix achten). Es gibt keine Bibliotheksimplementierung des Algorithmus in der .NET-Plattform, die Sie direkt aufrufen können, aber der hier verlinkte Artikel ist randvoll mit Schritten, wie Sie es selbst tun würden.

Ich wollte ein gemeinsames String-Präfix, außer dass ich ein beliebiges Zeichen (wie /) einfügen wollte und ich wollte nicht etwas performantes / schickes etwas, was ich mit Tests lesen kann. Also ich habe das: https://github.com/fschwiet/DreamNJasmine/commit/ad802611ceacc673f2d03c30f7c8199f552b586f

 public class CommonStringPrefix { public static string Of(IEnumerable 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; } } 

Hier ist eine benutzerdefinierte Implementierung des Trie-Algorithmus in c # ( http://en.wikipedia.org/wiki/Trie ). Es wird verwendet, um eine indizierte Zeichenfolge über Präfixe durchzuführen. Diese class hat O (1) schreiben und liest für Blattknoten. Für Präfixsuchen ist die performance O (log n), die Anzahl der Ergebnisse für Präfix ist jedoch 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 _rootChars; public StringIndex() { _rootChars = new Dictionary(); } public void Add(string value, string data) { int level = 0; Dictionary 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 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 currentChars = _rootChars; Dictionary 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 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 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 GetValuesByPrefixFlattened(string prefix) { var results = GetValuesByPrefix(prefix); return new HashSet(results.SelectMany(x => x)); } public List> GetValuesByPrefix(string prefix) { var values = new List>(); int level = 0; Dictionary 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> 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 Values { get; set; } public Dictionary Items { get; set; } public Item() { Values = new HashSet(); Items = new Dictionary(); } } } 

Hier ist der Unit-Test & Beispielcode für die Verwendung dieser class.

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

Vorschläge zur Verbesserung dieser class sind willkommen 🙂

Mein Ansatz wäre, nimm die erste Saite. Erhalten Sie Buchstabe für Buchstabe, während alle anderen Zeichen den gleichen Buchstaben an der gleichen Indexposition erhalten, und halten Sie an, wenn keine Übereinstimmung vorhanden ist. Entfernen Sie das letzte Zeichen, wenn es sich um ein Trennzeichen handelt.

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

Ich musste nach dem längsten gemeinsamen Präfix in verschiedenen Strings suchen. Ich hatte die Idee dass:

 private string FindCommonPrefix(List list) { List 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(x); } return prefixes == null ? string.Empty : prefixes.First(); } 

Wenn es mehr als ein Präfix mit der gleichen Länge gibt, gibt es willkürlich das erste gefundene zurück. Es ist auch Groß-und Kleinschreibung. Beide Punkte können vom Leser angesprochen werden!

Ich habe diese ICollection-Erweiterung geschrieben, um aus einer Sammlung von Webadressen die längste gemeinsame Basis-Uri zu finden.

Da es nur die Sammlung von Zeichenfolgen bei jedem Schrägstrich überprüft, wird es ein bisschen schneller sein als eine generische Präfix-Routine (meinen ineffizienten Algorithmus nicht mitgezählt!). Es ist ausführlich, aber einfach zu folgen … meine Lieblingsart des Codes 😉

Ignoriert ‘http: //’ und ‘https: //’ sowie Groß- / Kleinschreibung.

  ///  /// Resolves a common base Uri from a list of Uri strings. Ignores case. Includes the last slash ///  ///  /// Common root in lowercase public static string GetCommonUri(this ICollection 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; } 

Die obere Antwort kann verbessert werden, um den Fall zu ignorieren:

 .TakeWhile(s => { var reference = s.First(); return s.All(d => string.Equals(reference, d, StringComparison.OrdinalIgnoreCase)); })