查找常规字符串前缀

赞同来自:

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>&gt; Transpose<t>/

 this IEnumerable<ienumerable<t>&gt; source/

{

 var enumerators = source.Select/e =&gt; e.GetEnumerator///.ToArray//;

 try

 {

 while /enumerators.All/e =&gt; e.MoveNext////

 {

 yield return enumerators.Select/e =&gt; e.Current/.ToArray//;

 }

 }

 finally

 {

 Array.ForEach/enumerators, e =&gt; e.Dispose///;

 }

}

</ienumerable<t></t></ienumerable<t>

董宝中

赞同来自:

缩短解决方案 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;

喜特乐

赞同来自:

基于Sam Herder决定的工作代码 /注意它给出 h:/a/ 不是 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]

 }

 }

}

卫东

赞同来自:

这是最多的

http://en.wikipedia.org/wiki/L ... oblem
/虽然它是一个小小的案例，因为你似乎只关心前缀/. 在平台上 .NET 没有图书馆实现您可以直接导致的算法，但在此处连接的文章，列通过关于您自己的方式的步骤包装。

卫东

赞同来自:

以下是算法的用户实现
http://en.wikipedia.org/wiki/Trie
Tri. /.
它用于使用前缀执行索引字符串。这堂课有 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 =&gt; x//;

 }



 public List<hashset<string>&gt; GetValuesByPrefix/string prefix/

 {

 var values = new List<hashset<string>&gt;//;



 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>&gt; 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"/ &amp;&amp; output.Contains/"2"/ &amp;&amp; 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"/ &amp;&amp; output.Contains/"2"/ &amp;&amp; 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 &amp;&amp; output2 == 2 &amp;&amp; output3 == 2 &amp;&amp; output4 == 0/;

 }

 }

欢迎有关如何改进此类课程的任何建议。 :/
</char,></string></char,></string></hashset<string></char,></hashset<string></hashset<string></string></string></char,></char,></char,></char,></char,></char,></char,></char,>

三叔

赞同来自:

我需要一个共享字符串前缀，除了我想要包含任何符号。 /例如， //, 而且我不想要富有成效的东西/花哨，只是在测试的帮助下可以阅读的东西。所以，我有这个：
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 &lt; commonPrefix.Length/

 commonPrefix = commonPrefix.Substring/0, potentialMatchLength/;



 for/var i = 0; i &lt; potentialMatchLength; i++/

 {

 if /s[i] != commonPrefix[i]/

 {

 commonPrefix = commonPrefix.Substring/0, i/;

 break;

 }

 }

 }



 return commonPrefix;

 }

}

</string>

窦买办

赞同来自:

我的方法就是：拿第一个字符串。
把信超出这封信，而所有其他行就是在同一位置的相同位置收到相同的信件，如果没有巧合。
如果是分隔符，请删除最后一个字符。

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

龙天

赞同来自:

我需要在不同行中找到最长的常见前缀。我想到了：

private string FindCommonPrefix/List<string> list/

{

 List<string> prefixes = null;

 for /int len = 1; ; ++len/

 {

 var x = list.Where/s =&gt; s.Length &gt;= len/

 .GroupBy/c =&gt; c.Substring/0,len//

 .Where/grp =&gt; grp.Count// &gt; 1/

 .Select/grp =&gt; grp.Key/

 .ToList//;



 if /!x.Any///

 {

 break;

 }

 // Copy last list

 prefixes = new List<string>/x/;

 }



 return prefixes == null ? string.Empty : prefixes.First//;

}

如果长度超过一个以上的前缀，则会随机返回找到的第一个。此外，它对寄存器很敏感。读者可以考虑这些物品中的两项。
</string></string></string>

三叔

赞同来自:

我写了这个扩张 ICollection, 找到总基数最长的基础 Uri 来自网址的集合。

由于它只检查每层一组行，因此它将比通常的前缀程序快一点 /不计算我的低效算法！/. 这是一个口头，但很容易 follow...my 最喜欢的代码类型 ;-/

忽略 'http://' 和 ' https://', 以及登记册。

/// <summary>

 /// Resolves a common base Uri from a list of Uri strings. Ignores case. Includes the last slash

 /// </summary>

 /// <param name="collectionOfUriStrings"/>

 /// <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 &gt; minPos ? firstUri.Substring/0, previousSlashPos + 1/.ToLower// : string.Empty ;

 }

 }

 previousSlashPos = nextSlashPos; 

 nextSlashPos = firstUri.IndexOf/"/", previousSlashPos + 1, StringComparison.OrdinalIgnoreCase/;

 } while /nextSlashPos != -1/;



 return previousSlashPos &gt; minPos ? firstUri.Substring/0, previousSlashPos + 1/.ToLower// : string.Empty;

 }

</string>

裸奔

赞同来自:

在这里，我已经实施了一个相当有效的方法，当您必须分析大量的行数时，我也缓存了数量和长度，这提高了大约的性能 1,5 与访问循环中的属性相比，我的测试中的3次：

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 &lt; stringsCount; i++ /

 {

 str = strings[i];



 sbLen = sb.Length;

 strLen = str.Length;

 if/ sbLen &gt; strLen /

 sb.Length = sbLen = strLen;



 for/ j = 0; j &lt; 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,

 // =&gt; new StringBuilder/ firstStr /,

 / i, loop, localSb / =&gt;

 {

 var sbLen = localSb.Length;

 var str = strings[i];

 var strLen = str.Length;

 if/ sbLen &gt; strLen /

 localSb.Length = sbLen = strLen;



 for/ int j = 0; j &lt; sbLen; j++ /

 {

 if/ localSb[j] != str[j] /

 {

 localSb.Length = j;

 break;

 }

 }



 return localSb;

 },

 / localSb / =&gt;

 {

 lock/ finalListLock /

 {

 finalList.Add/ localSb.ToString// /;

 }

 } /;



 return GetCommonPrefix/ finalList /;

}

GetCommonPrefixParallel// 与...相比增加了两倍 GetCommonPrefix// 在大量的行中，并且具有大量的线条。在带有短线的小阵列上 GetCommonPrefix// 它有效好一点。我在测试 MacBook Pro Retina 13".
</string></string></string>

莫问

赞同来自:

这是一个发现共享字符串前缀的简单方法。

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;

 }

三叔

赞同来自:

提高Egor的响应

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 要么持续或减少。在第一次迭代的电流中 - 这是最小元素，但每个后续迭代 - 这是最好的 commonPrefix, 到目前为止发现。将其视为基于深度的解决方案，而第一个是基于宽度的解决方案。

通过将样品的长度分选，可以提高这种类型的解决方案，使得最短的元件是比较最短的元件。

然而，这种类型的决定不能比第一个更好。最多，这与第一个决定一样好。但其他，他会做额外的工作，找到临时 commonPrefixes, 这比必要的时间长。

卫东

赞同来自:

我为派对迟到了，但我会给我的 2 美分：

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

}

解释：

它有效，通过角色

str

直到

All

其他线条具有相同的符号

在索引中

.

分离签名

String

和

params String[]

它保证将提供至少一条线路，并且在执行期间不需要检查。

如果仅使用一个字符串调用该函数，则返回输入数据 /线 - 这是她自己的前缀/.

更便宜

Count

前缀长度和退款

Substring/0, prefixLength/

, 使用什么重新收集列出的字符

String.Join//

或者

Enumerable.Aggregate//

窦买办

赞同来自:

顶部答案可以得到改进以忽略这种情况：

.TakeWhile/s =>

 {

 var reference = s.First//;

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

 }/

查找常规字符串前缀

15 个回复

发起人

相关问题

问题状态

查找常规字符串前缀

与内容相关的链接

15 个回复

发起人

相关问题

问题状态