在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个字符串中以相同顺序设置的字符集

回答

相关问题