字符串解析並找到常見的空白位置

Question

我想解析一個字符串並找到一個常見的空白位置。

這裏是我的琴絃

abc xyz 123 456 
cba 1234a 45623 say 
avc 4567 bv 456 

可以有任意數量的字符串。我需要一個通用的算法在c＃中更好，我可以在上面的字符串中找到常見的空白位置。

例如，在上述的串常見的位置是

4, 10 ,16 

其具有在每一個串的白色空間。

方法我一直在嘗試包括相交，並獲得所有可能的空間，然後比較找出常見的，但我試圖找出最佳的解決方案。

Answer 1

var stringList = new[] { "abc xyz 123 456", "cba 1234a 45623 say", "avc 4567 bv 456" }; 
var shortest = stringList.OrderBy(s => s.Length).First(); 
var result = new Collection<int>(); 

for (int i = 0; i < shortest.Length; i++) 
{ 
    if (stringList.All(c => c[i] == ' ')) result.Add(i+1); 
} 

// Test the results 
foreach (var index in result) 
{ 
    Console.WriteLine(index); 
} 

Answer 2

在第一個字符串中創建一組空白位置。檢查第二次刺戳中的位置，如果第二個字符串中該位置的字符不是空白，則從該集合中刪除該位置。重複其餘的字符串。

另一種可能性是找到每個字符串中空白位置的集合，然後找到這些集合的交集。這將有一個潛在的優勢。雖然這通常會完成更多的總體工作，但部分工作（查找單個集合）很容易並行執行。我懷疑這會贏得很多，但是（除非，也許你有很多字符串和很多內核）。雖然它可能不那麼明顯，但您也可以同時找到所設置的交點 - 您基本上會執行交叉點的二叉樹，因此在第一次迭代中可以找到交點之間的交點，然後在第二次找到結果對之間的交點從第一次迭代開始，等等，直到你只剩下一組。假設至少有許多核心作爲字符串，這將時間複雜度從O（N）減少到O（log N）。