Trie＆子序列

我們有兩個集合A和B.每個集合都包含字符串。例如：A - {「abwcd」，「dwas」，「www」}和B - {「opqr」，「tops」，「ibmd」} 如何計算出現在集合A中所有字符串中的子序列，但是在集合B中沒有任何字符串？對於上面的例子，答案是1（子序列「w」）。Trie＆子序列

所有這一切都以最佳方式進行。我想過使用兩次嘗試，第一次將所有字符串的所有子序列都放在B中的t_B中，然後我開始將所有字符串的所有子序列都放在A中的t_A中，而不更新如果相同子序列之前在同一個字符串中被找到（例如：如果我有字符串「aba」，我不計算子序列「a」兩次）。這樣，如果我找到一個在t_A中出現的子序列，我檢查它是否在t_B中，如果不是，我計算它。但是這非常慢，如果A和B的大小爲15，字符串長度大約爲100個字符，我的程序運行時間超過1秒。由於任何subsqeunce都以字符串的最後一個字符結尾或在它之前的一個字符中結束，因此我們不必生成所有子序列，而是生成以字符串的最後一個字符結尾的子序列。當我將它們推入特里時，我注意到每個節點都是1.因此，如果我有字符串「abcd」，我只需按「abcd」，「bcd」，「cd」和「d」，因爲這應該是'骨架'的特里。但這不是一個很大的優化，我仍然在尋找更好的東西。

來源

2012-03-13 Robert Badea

我並不感到驚訝您的解決方案是有點慢，您所描述的算法運行時間n^2的量級。通常，像這樣的問題，動態編程是一個好方法。但從算法的角度來看，子序列問題是非常困難的，所以n^2可能是你所期望的最好的。 – pg1989 2012-03-13 20:26:28

是的，n^2是我能想到的最好的，然後我考慮了一個優化，因爲任何subsqeunce都以字符串的最後一個字符或之前的字符結尾，所以現在我不生成所有的子序列，但是以字符串的最後一個字符結尾的那些字符串，當我將它們推入trie中時，我注意到每個節點都帶有1，它是新的，或者如果它已經存在，則增加它。所以如果我有字符串「abcd」，我只推送「abcd」，「bcd」，「cd」和「d」，因爲這應該是trie的「骨架」。但這不是一個很大的優化，我仍然在尋找更好的東西。 – 2012-03-13 20:38:42

我認爲它更好地調用這些子字符串，而不是子序列。子序列是我們唯一可以通過刪除一些元素而不改變剩餘元素的順序從另一個序列派生的序列。 – 2013-08-08 19:05:49

你不應該把所有的字符串的所有子序列在阿成的線索。只能放入有效的。在添加序列之前測試序列是否有效。我假設會員測試比添加新項目更快。較小的特洛伊木馬應該會更快地失敗成員測試，所以此策略旨在儘可能快地減少特洛伊木馬。

具體來說：將A中第一個字符串的所有子序列放入trie中。（爲了提高效率，請使用最短的字符串作爲第一個字符串）。保留一組對所有葉節點的引用。接下來，對於B中的所有字符串，測試每個子序列以查看它是否存在於A中。如果是，則刪除該序列並且它是引用。（從B中最長的字符串開始，儘可能快地刪除trie）。

現在你有最少的一組可能要測試的。對於A中所有剩餘的字符串，測試每個子序列以查看它是否存在於trie中。如果是，則將節點標記爲有效，否則移至下一個子序列。在每個字符串之後，從trie中刪除所有無效節點，並將其餘的標誌重置爲無效。

來源

2012-03-13 20:47:00 AShelly

回答

相關問題