У меня есть 4 строки:
"h:/a/b/c"
"h:/a/b/d"
"h:/a/b/e"
"h:/a/c"
Я хочу найти общий префикс для этих строк, т.е. "h:/a".
Как это найти?
Обычно я бы разделил строку с разделителем '/' и поместил ее в другой список и т.д.
Есть ли лучший способ сделать это?
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()));
с
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());
}
}
Краткое мое решение 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());
Просто обведите вокруг символов кратчайшей строку и сравните каждый символ с символом в том же положении в других строках. Пока они все поддерживают. Как только один не совпадает, строка соответствует текущей позиции -1.
Что-то вроде (псевдокод)
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;
Рабочий код, основанный на решении Сэма Холдера (обратите внимание, что он дает h:/a/not h:/a как самую длинную общую начальную подстроку в вопросе):
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]
}
}
}
Это самая длинная распространенная проблема с подстрокой (хотя это немного специализированный случай, так как кажется, что вы заботитесь только о префиксе). В платформе .NET нет библиотечной реализации алгоритма, которую вы можете вызвать напрямую, но статья, на которую вы ссылаетесь, полна шагов о том, как вы это сделаете сами.
Мне нужен общий префикс строки, за исключением того, что я хотел включить любой символ (например,/), и я не хотел, чтобы что-то показало, что я могу читать с помощью тестов. Поэтому у меня есть это: 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;
}
}
Вот пользовательская реализация алгоритма trie в С# (http://en.wikipedia.org/wiki/Trie). Он используется для выполнения индексированной строки через префиксы. Этот класс O (1) записывает и читает для листовых узлов. Для поиска в префиксах производительность O (log n), однако количество результатов для префикса равно 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>();
}
}
}
Ниже приведен пример модульного тестирования и пример кода для использования этого класса.
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);
}
}
Любые предложения по улучшению этого класса приветствуются:)
Мой подход будет, возьмите первую строку. Получайте письмо по букве, а вся другая строка получает ту же букву в той же позиции индекса и останавливается, если нет совпадения. Удалите последний символ, если он разделитель.
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 a separator (optional)
if (ret.LastOrDefault() == separator)
ret = ret.Take(ret.Count() -1);
string prefix = new String(ret.ToArray());
Мне нужно было найти самый длинный общий префикс в несходных строках. Я придумал:
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();
}
Если существует более одного префикса с одинаковой длиной, он произвольно возвращает первый найденный. Также он чувствителен к регистру. Оба эти точки могут быть решены читателем!
Я написал это расширение ICollection, чтобы найти самую длинную общую базу Uri из коллекции веб-адресов.
Поскольку он проверяет только коллекцию строк при каждой косой черте, это будет немного быстрее, чем обычная префиксная процедура (не считая мой неэффективный алгоритм!). Это многословно, но легко следовать... мой любимый тип кода; -)
Игнорирует "http://" и "https://", а также случай.
/// <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;
}
Верхний ответ может быть улучшен, чтобы игнорировать регистр:
.TakeWhile(s =>
{
var reference = s.First();
return s.All(d => string.Equals(reference, d, StringComparison.OrdinalIgnoreCase));
})
Здесь я реализовал довольно эффективный метод, когда вы должны анализировать огромное количество строк, здесь я также кеширую количество и длину, что повышает производительность примерно в 1,5 раза в моих тестах по сравнению с доступом к свойствам в циклах:
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: я также реализовал параллельную версию, которая использует вышеуказанный метод в качестве последнего шага:
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() повышает в два раза по сравнению с GetCommonPrefix() при большом количестве строк и значительных длинах строк. На небольших массивах с короткими строками GetCommonPrefix() работает немного лучше. Я тестировал на MacBook Pro Retina 13 ''.
Это простой метод, который находит общий префикс строки.
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 result;
}
Улучшение ответа Егора
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());
Сначала мы знаем, что самый длинный общий префикс не может быть длиннее самого короткого элемента. Поэтому возьмите самый короткий и возьмите из него символы, в то время как все другие строки имеют одинаковый символ в той же позиции. В крайнем случае мы берем все символы из самого короткого элемента. Итерируя по самому короткому элементу, поиск по индексу не вызовет никаких исключений.
Другой (хуже, но все же интересный) способ решить эту проблему с помощью LINQ был бы следующим:
samples.Aggregate(samples.Min(), (current, next) => new string(current.TakeWhile((c,i) => next[i] == c).ToArray() ));
Это работает путем создания commonPrefix и сравнения его с каждым элементом по одному. В каждом сравнении commonPrefix либо поддерживается, либо уменьшается. В первой итерации текущим является элемент min, но после каждой итерации он является лучшим из общего CommonPrefix, найденного до сих пор. Думайте об этом как о глубоком решении, а первое - ширине.
Решение этого типа можно улучшить, отсортировав образцы по длине, чтобы сначала сравнивались самые короткие элементы.
Однако этот тип решения не может быть лучше первого. В лучшем случае это так же хорошо, как и первое решение. Но в противном случае он будет выполнять дополнительную работу, находя временные общие префиксы, которые длиннее, чем необходимо.