生成列表與其所有後綴之間的所有最長公共前綴

Question

讓lcp是生成兩個列表之間的最長公共前綴數的函數。

例如lcp [1;2;3;1;2] [1;2] = 2。

---

對於給定的列表，它有n非空後綴，包括它本身。

例如，

的所有後綴[1; 2; 1 3]：

[1; 2; 3]
[2; 3]
[3]

---

這裏的問題是生成list和all its own suffixes之間的所有lcp。

這裏我們談論的是A和A的所有後綴。沒有列表B存在。

例如，用於列表[1;2;3]，我想值的列表和每個值是

分別llcp [1;2;3] [1;2;3]

llcp [1;2;3] [2;3]

llcp [1;2;3] [3]

。即，結果應該是[3; 0; 0]

---

它是直接使用蠻力，但它採取O(n^2)。

如何在O（n）？不要使用後綴樹或後綴數組。

---

編輯

我認爲這是絕對有可能做到爲O（n）。我還沒有完全弄清楚，但是我發現了一些有趣的東西。

例如，我們有[x1;x2;x3;x4;x5;x6]，那麼它的所有後綴

row1: [x1;x2;x3;x4;x5;x6]

row2: [x2;x3;x4;x5;x6]

row3: [x3;x4;x5;x6]

row4: [x4;x5;x6]

row5: [x5;x6]

row6: [x6]

我們的目標是計算

lcp row1 row1（顯然是N）

lcp row1 row3

lcp row1 row4

lcp row1 row5

lcp row1 row6

---

所以讓我們嘗試第一。

如果我們說lcp row1 row2 = 3，這意味着x1=x2; x2=x3; x3=x4; x4<>x5，對吧？

那麼我們可以從上面的比較中得到什麼？

我們可以知道

• x1 = x3; x2 = x4; x3 <> x5，對不對？那麼馬上我們得到lcp row1 row3 = 2，對吧？
• x1 = x4; x2 <> x5，對不對？然後立即lcp row1 row4 = 1
• x1 <> x5，然後立即lcp row1 row5 = 0

而且只有lcp row1 row6剩下要做的。

這裏的關鍵我想是平等轉讓，也可以不均通過局部平等信息

Answer 1

計算Z-功能列表（治療就像是一個字符串，每個元素作爲一個字符）。那麼從第i個位置開始的後綴的答案是z（i）。應該很容易在O（n）中找到z函數算法的實現。 這是我的O（n）實現。

public static List<Integer> getLcp(List<Integer> input) { 
      Integer[] lcp = new Integer[input.size()]; 
      Arrays.fill(lcp, input.size()); 
      int left = 1; 
      int right = -1; 
      for (int pos = 1; pos < input.size(); pos++) { 
        if (pos <= right) 
          lcp[pos] = Math.min(lcp[pos - left], right - pos + 1); 
        else 
          lcp[pos] = 0; 
        while (pos + lcp[pos] < input.size() && 
            input.get(pos + lcp[pos]) == input.get(lcp[pos])) 
          lcp[pos]++; 
        if (pos + lcp[pos] - 1 > right) { 
          left = pos; 
          right = pos + lcp[pos] - 1; 
        } 
      } 
      return Arrays.asList(lcp); 
    } 

Answer 2

我不認爲這是可能的O（N）來解決被引導。 但是你可以做一個很好的優化。

我會提出一些臨客這樣的：

• 首先獲得元件1的最大後綴和2
• 然後得到的一個結果和元素之間的最大後綴3
• 直到你到達下去結束

在大多數情況下，在處理了前幾個元素後，後綴應該變成一個非常短的字符串，然後您不必比較多個字符。 這個想法是，當元素1和2有一個n長的後綴時，全局後綴最多可以是n長（但可以更短）。

---

編輯：

好吧，我想我現在明白你的問題：d 但我想不出一個爲O（n）十字的。 這是我最好的嘗試（不幸的是在C＃中，因爲目前我沒有Java的IDE此計算機上...）

static void Main(string[] args) 
{ 
    Console.WriteLine(string.Join(" ", llcp(new List<char> { 'A', 'B', 'C', 'A', 'A', 'B' }).Select(p => p.ToString()).ToArray())); 

    Console.ReadLine(); 
} 

static List<int> llcp(List<char> elements) 
{ 
    List<int> result = new List<int>(); 
    for (int i = 0; i < elements.Count; i++) 
    { 
     int j; 
     for (j = 0; j < elements.Count; j++) 
      if (i+j >= elements.Count || elements[i+j] != elements[j]) 
       break; 
     result.Add(j); 
    } 
    return result; 
} 
//Output: 6 0 0 1 2 0 

所以它應該是優化和林不知道如果你可以讓IST顯著更快（想法明智的，也許你可以優化的幾點思考執行）

MFG邁克