Znajdź wspólny prefiks ciągu

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

od

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

 }

}

Skróć moje rozwiązanie 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());

Po prostu zakreśl znaki najkrótszego ciągu i porównaj każdy znak ze znakiem w tej samej pozycji w innych wierszach. Dopóki wszyscy pasują, idź dalej. Jak tylko jeden z nich się nie zgadza, odpowiedzią jest linia do bieżącej pozycji -1.
Coś jak (pseudokod)

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;

Działający kod oparty na rozwiązaniu Sama Holdera (zwróć uwagę, że podaje h:/a/nie h:/a jako najdłuższy wspólny podciąg początkowy w pytaniu):

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]

 }

 }

}

To jest najbardziej
długi wspólny problem z podciągami
http://en.wikipedia.org/wiki/L ... oblem

(chociaż jest to trochę wyspecjalizowany przypadek, ponieważ wydaje się, że obchodzi cię tylko prefiks). W architekturze .NET nie ma biblioteki implementacji algorytmu, którą można wywołać bezpośrednio, ale artykuł, do którego prowadzi łącze, zawiera mnóstwo instrukcji dotyczących samodzielnego wykonywania tych czynności.

Oto niestandardowa implementacja algorytmu

spróbuj w c # (http://en.wikipedia.org/wiki/
http://en.wikipedia.org/wiki/Trie
Trewir).
Służy do wykonania zindeksowanego ciągu przy użyciu prefiksów. Ta klasa ma O (1) do zapisu i odczytu dla węzłów liści. W przypadku wyszukiwania prefiksu wydajność wynosi O (log n), jednak liczba wyników dla prefiksu wynosi 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>();

 }

 }

}

Oto przykład testowania jednostkowego kodu & amp; o tym, jak korzystać z tej klasy.

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

 }

 }

Wszelkie sugestie dotyczące ulepszenia tej klasy są mile widziane :)

Potrzebowałem ogólnego prefiksu ciągu, z wyjątkiem tego, że chciałem dołączyć dowolny znak (taki jak/) i nie chciałem niczego wydajności/fantazyjności, po prostu coś, co mogę przeczytać za pomocą testów. Więc mam to:

https://github.com/fschwiet/Dr ... b586f
https://github.com/fschwiet/Dr ... b586f

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;

 }

}

Moje podejście polegałoby na przyjęciu pierwszej struny.
Pobierz litera po literze, podczas gdy wszystkie inne linie mają tę samą literę na tej samej pozycji indeksu i zatrzymują się, jeśli nie ma dopasowania.
Usuń ostatni znak, jeśli jest separatorem.

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

Musiałem znaleźć najdłuższy wspólny prefiks w różnych ciągach. Rozgryzłem to:

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

}

Jeśli istnieje więcej niż jeden prefiks o tej samej długości, zwraca losowo pierwszy znaleziony. Ponadto rozróżnia się wielkość liter. Czytelnik może wziąć pod uwagę oba te punkty!

Napisałem to rozszerzenie ICollection, aby znaleźć najdłuższy udostępniony Uri ze zbioru adresów internetowych.
Ponieważ sprawdza tylko kilka ciągów znaków przy każdym ukośniku, będzie to nieco szybsze niż zwykła procedura prefiksu (poza moim nieefektywnym algorytmem!). Jest rozwlekły, ale łatwy do naśladowania ... mój ulubiony typ kodu ;-)
Ignoruje „http://” i „https://”, a także wielkość liter.
<pre class="lang-cs prettyprint-override">

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

 }

Tutaj zaimplementowałem dość wydajną metodę, gdy musisz przeanalizować ogromną liczbę linii, tutaj również buforuję liczbę i długość, co poprawia wydajność około 1,5 razy w moich testach w porównaniu z dostępem do właściwości w pętlach:

using System.Collections.Generic;

using System.Text;........public static string GetCommonPrefix ( IList<string> strings )

{

 var stringsCount = strings.Count;

 if( stringsCount == 0 )

 return null;

 if( stringsCount == 1 )

 return strings[0]; var sb = new StringBuilder( strings[0] );

 string str;

 int i, j, sbLen, strLen; for( i = 1; i < stringsCount; i++ )

 {

 str = strings[i]; sbLen = sb.Length;

 strLen = str.Length;

 if( sbLen > strLen )

 sb.Length = sbLen = strLen; for( j = 0; j < sbLen; j++ )

 {

 if( sb[j] != str[j] )

 {

 sb.Length = j;

 break;

 }

 }

 } return sb.ToString();

}

UPD:

Zaimplementowałem również wersję równoległą, która wykorzystuje powyższą metodę jako ostatni krok:

using System.Collections.Generic;

using System.Text;

using System.Threading.Tasks;........public static string GetCommonPrefixParallel ( IList<string> strings )

{

 var stringsCount = strings.Count;

 if( stringsCount == 0 )

 return null;

 if( stringsCount == 1 )

 return strings[0]; var firstStr = strings[0];

 var finalList = new List<string>();

 var finalListLock = new object(); Parallel.For( 1, stringsCount,

 () => new StringBuilder( firstStr ),

 ( i, loop, localSb ) =>

 {

 var sbLen = localSb.Length;

 var str = strings[i];

 var strLen = str.Length;

 if( sbLen > strLen )

 localSb.Length = sbLen = strLen; for( int j = 0; j < sbLen; j++ )

 {

 if( localSb[j] != str[j] )

 {

 localSb.Length = j;

 break;

 }

 } return localSb;

 },

 ( localSb ) =>

 {

 lock( finalListLock )

 {

 finalList.Add( localSb.ToString() );

 }

 } ); return GetCommonPrefix( finalList );

}

GetCommonPrefixParallel () podwaja się w porównaniu z GetCommonPrefix () na ogromnej liczbie linii i przy znacznych długościach linii. GetCommonPrefix () działa nieco lepiej na małych tablicach z krótkimi łańcuchami. Testowałem na MacBooku Pro Retina 13 ".

Jest to prosta metoda znajdowania wspólnego przedrostka ciągu.

public static string GetCommonStartingPath(string[] keys)

 {

 Array.Sort(keys, StringComparer.InvariantCulture);

 string a1 = keys[0], a2 = keys[keys.Length - 1];

 int L = a1.Length, i = 0;

 while (i < L && a1[i] == a2[i])

 {

 i++;

 } string result = a1.Substring(0, i); return resu<

 }

Poprawa odpowiedzi Egora

var samples = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/e" };var commonPrefix = new string( samples.Min().TakeWhile((c, i) => samples.All(s => s[i] == c)).ToArray());

Po pierwsze, wiemy, że najdłuższy wspólny prefiks nie może być dłuższy niż najkrótszy element. Więc weź najkrótszą i weź z niej znaki, podczas gdy wszystkie inne linie mają ten sam znak w tej samej pozycji. W ostateczności bierzemy wszystkie postacie z najkrótszego elementu.
Podczas iteracji po najkrótszym elemencie wyszukiwanie indeksu nie zgłosi żadnych wyjątków.
Innym (gorszym, ale wciąż interesującym) sposobem rozwiązania tego problemu za pomocą LINQ byłby następujący:

samples.Aggregate(samples.Min(), (current, next) => new string(current.TakeWhile((c,i) => next[i] == c).ToArray() ));

Ta metoda działa poprzez utworzenie commonPrefix i porównanie go z każdym elementem jeden po drugim. W każdym porównaniu commonPrefix zostaje zachowany lub zredukowany. W pierwszej iteracji prąd jest elementem minimalnym, ale każda kolejna iteracja jest najlepszym znalezionym do tej pory commonPrefix. Potraktuj to jako rozwiązanie oparte na głębokości, podczas gdy to pierwsze jest rozwiązaniem opartym na szerokości.
Tego typu rozwiązanie można ulepszyć, sortując próbki według długości, tak aby najpierw porównywane były najkrótsze elementy.
Jednak tego typu rozwiązanie naprawdę nie może być lepsze od pierwszego. W najlepszym przypadku jest to tak dobre, jak pierwsze rozwiązanie. Ale w przeciwnym razie wykona dodatkową pracę, znajdując tymczasowe wspólne poprawki, które są dłuższe niż to konieczne.

Spóźniłem się na imprezę, ale dam 2 centy:

public static String CommonPrefix(String str, params String[] more)

{

 var prefixLength = str

 .TakeWhile((c, i) => more.All(s => i < s.Length && s[i] == c))

 .Count(); return str.Substring(0, prefixLength);

}

Wyjaśnienie:

• Działa to poprzez zapętlenie znaków

  str

  , o ile

  All

  pozostałe ciągi mają ten sam znak

  c

  w indeksie

  i

  .
• Rozdzielenie podpisów na

  String

  i

  params String []

  zapewnia, że ​​podano przynajmniej jeden ciąg i nie są wymagane żadne sprawdzenia w czasie wykonywania.
• Jeśli funkcja jest wywoływana tylko z jednym ciągiem, zwraca dane wejściowe (ciąg jest własnym prefiksem).
• Taniej jest

  Count

  długość prefiksu i zwrócenie

  Substring (0, prefixLength)

  niż ponowne złożenie wymienionych znaków za pomocą

  String.Join ()

  lub < code> Enumerable.Aggregate ()

Najlepszą odpowiedź można poprawić, aby zignorować przypadek:

.TakeWhile(s =>

 {

 var reference = s.First();

 return s.All(d => string.Equals(reference, d, StringComparison.OrdinalIgnoreCase));

 })