找到給定的兩個字符串的所有常見子序列

-1

我試過使用LCS（最長公共子序列）算法，但我想要所有長度的子序列。我們如何修改LCS代碼？找到給定的兩個字符串的所有常見子序列

例：鑑於String_1="abxcd"和"abcd"String_2="aybcd" LCS的結果，但我想顯示{ 「一」，「AB」，「BCD」，「CD」，「ABCD」，「d」}

2014-03-19 Sanjana

歡迎SO - http://stackoverflow.com/help/how-to-ask –

你在[最長公共子序列]興趣（HTTP ：//en.wikipedia.org/wiki/Longest_common_subsequence_problem）或[Longest common substring problem]（http://en.wikipedia.org/wiki/Longest_common_substring_problem）？ – Harmlezz

我想要兩個字符串的所有子序列示例：String_1 =「abxcd」和String_2 =「aybcd」LCS將給出「abcd」但我想顯示a，ab，bcd，cd，abcd，d – Sanjana

試試這個僞代碼

Set allCS;//create an empty set 
String[] subStrings = getSubSequences(String_2) //find the subsequence of String_2 
for (String str : subStrings) 
    allCS.put(LCS(String_1,str)) //add LCS of (String_1,str) to allCS

注：

getSubSequences(String s)返回給定字符串parame的所有子之三
LCS(String s1, String s2)返回S1 S中的LCS和

來源

2014-03-19 10:36:47 mok

我期望子序列不會子。 – Sanjana

@ Sanjana-我剛剛編輯了我的答案，你可以看到一般的方法是一樣的。 – mok

我試過這樣做，但對於更長的字符串，我不認爲這可以解決。你能否以其他方式建議我這麼做？ – Sanjana

找到給定的兩個字符串的所有常見子序列

回答

相關問題