我可以檢查是否子序列更快然後O（n * n）

所以我的問題是在主題的名稱。是否存在一種算法，用於檢查B是否比O（N^2）更快，例如O（NlogN）或者簡單地O（N）是否是A的子序列？我可以檢查是否子序列更快然後O（n * n）

唯一的方法發現是簡單的香檳力

for(int i = 0; i < a.Length - b.Length; i++) 
{ 
    if (IsSubsequence(a,b,i)) 
     return i; 
} 
return -1;

應該定義子序列和舉一個例子，以避免混亂的長度。請加上你的代碼'IsSubsequence'請 –

因爲通常子序列意味着你看起來要求的東西不同 –

下面是David Eisenstat算法的遞歸表徵。（請注意，該算法是尾遞歸並且因此可以被寫爲一個循環;我將它描述爲遞歸的，因爲這樣做是一個很好的方式來理解的算法。）

定義一個序列作爲空的，或項目後跟一個序列。

取兩個序列A和B的問題是，如果B是或不是A的一個子序列

如果B是空的，則B是A的一個子序列

如果B不空和A是空的，那麼B不是A的子序列。

如果我們已經做到了這一點，A和B都不是空的。假設A是項目X，後面是序列C，B是項目Y，後面是序列D.

如果X與Y相同，那麼問題的答案是「B是A的子序列？與對較小問題的答案是相同的「是D的一個子序列？」。回答這個問題。

如果X與Y不同，那麼問題的答案是B是A的子序列嗎？與較小問題的答案「是B的C子序列」是一樣的。回答這個問題。

這過程終止，並明確它的最壞的情況是在序列A.

2014-03-25 18:39:24

是的，這是可以做到快於O(n^2)與算法通過Knuth, Morris and Pratt。但請注意，framework提供的實現可能已經實現了此算法。

2014-03-25 14:39:09 Codor

子序列，而不是子字符串 –

我已經改變了鏈接到'Contains'方法而不是'Substring'方法的答案。你的意思是「子序列」完全不同的東西嗎？ – Codor

@Codor：子串是一種特殊的子序列。如果你有序列「A，B，C，D，E」，那麼「A，C，E」是一個子序列，但不是一個子串。「B，C，D」既是一個子序列又是一個子串。一個子串沒有「空白」。 KMP找到子字符串，而不是子序列。 –

是的，下面的貪心算法是正確的，並在時間O（n）運行。對於B的每個元素，從第一次出現的上一個停止點（最初是A的開始）開始，向前掃描A.

2014-03-25 14:39:16

當我們有兩個嵌套循環時，你如何得到O（n）？ –

@AlexJoukovsky它們是嵌套的，因爲這就是實現它們的方式，但是在一起，內部循環最多隻能通過A掃描一次。您可以將它們視爲非嵌套，並且控制流來回ping。 –

回答