在2個字符串中以相同順序設置的字符集

我有2個字符串，我們先調用一個基本字符串，然後再調用另一個字符串作爲輸入字符串。我正在努力設計一種算法，以查明輸入字符串內的基本字符串有多少個字符。這意味着並非所有來自基本字符串的字符都可能出現在輸入字符串中，但無論字符數是多少，都應該按順序排列（因爲它們出現在基本字符串中）我們需要找出基本字符串內部的匹配百分比輸入字符串在2個字符串中以相同順序設置的字符集

實施例：

base string: abcd 
input string: *a*b*c*d* 
output: 100% 

base string: abcd 
input string: *b*c*d* 
output: 75% 

base string: abcd 
input string: *a*c*d* 
output: 75% 

base string: abcd 
input string: *a*c*b*c*d* 
output: 75% (*a*c*d* or *b*c*d*) 

base string: abcd 
input string: *b*a*d*b*c*d* 
output: 100% (*a*b*c*d* is found)

來源

2017-02-23 arvind.mohan

在第四個示例中（'* a * c * b * c * d *'）不是'abcd'，因此您有100％的匹配？另外，你到目前爲止嘗試過什麼？ –

@SelçukCihan如果你在a和b中間忽略c，abcd就在那裏。它可以看作'（* a * b * c * d *）' –

基本字符串的最大長度是多少？ – fjardon

思維更上在此之後，這是一個典型的LCS問題。百分比可以通過LCS和輸入字符串/基本字符串的長度比例找出。

至於實現，我會使用Hirschberg算法。

來源

2017-02-23 11:10:11

在2個字符串中以相同順序設置的字符集

回答

相關問題