如何在使％字符分隔所有非连续匹配部分的同时输出两个字符串的匹配部分？

Question

我希望我可以为我一直在从事的项目提供一些帮助。给定两个字符串，我想输出这些字符串的匹配部分。此外，我希望匹配输出的任何非连续部分都由%符号分隔。

例如，如果我的两个字符串输入是：

• This is a test case see if it works 和
• test case it hopefully works

然后我想要的输出将是：

• test case%it%works

编辑：我已经写了我希望如何构造代码，但是需要一些帮助来微调确切的语法，任何帮助将不胜感激。我认为可以这样做：

string1 = A1 cell
string2 = B1 cell
output = ""
counter = 0
if LENGTH(string1) < LENGTH(string2) then split_string=string1 and other_string=string2             '
ELSE split_string=string2 and other_string=string1
matchable_values=split(split_string)
for each element in matchable_values      
    if ISNUMBER(SEARCH(element, other_string,counter)) then 
       output = output & element & %   and counter = counter + 
       LENGTH(element) + 1
     ELSEIF counter = counter + LENGTH(element) + 1
next element

return output

Answer 1

您尝试完成的工作并不容易，并且您需要一些高级开发技能（动态编程中的基础知识非常有用）。

实际上，您尝试做的工作与在生物信息学中比对DNA序列的想法相同。

因此，您需要做的是同时获取两个字符串（序列）

This is a test case, see if it works
test case, it hopefully works

并例如使用Needleman-Wunsch算法对齐它们（有更多已知的算法可以进行对齐）：

This is a test case, see if it ----------works
----------test case, -------it hopefully works

然后检查哪些字符相同，结果将是…

----------test case, -------it ----------works

然后用替换多个破折号，%同时从末尾开始删除破折号。因此，您的最终结果将是：

test case, %it %works

请注意，对于您的问题，没有一个确定的结果。永远会有更多结果！如果进行比对，则可能有不同的方法来比对2个序列。

因此，上述对齐方式的Needleman Wunsch回溯看起来像这样：

为什么没有简单的解决方案？

例如，我们采用以下2个字符串：

What output if this works?
What if this output works?

它们可以按以下方式对齐（按字排列）：

What output if this        works?
What        if this output works?

或作为

What         output if this works?
What if this output         works?

所以有2个结果

What % if this % works?
What % output % works?

他们是不同的。其他字符串可能有超过2种可能的结果。

因此，您需要一种可以给您所有可能结果的算法，然后您需要一种算法来确定哪一个是最好的（您想要拥有的）。在上述情况下，您如何判断2个结果中的哪一个是正确的？…你不能:)

再举一个例子：

我们使用以下2个字符串

to proove you wrong this is a good example for you
is this a good example to proove you wrong

可以（至少）对齐如下：

                       to prove you wrong this is a good example for you
is this a good example to prove you wrong


to prove you wrong this is a good example for you
                        is                        this a good example to prove you wrong

   to prove you wrong this is a good example          for you
is                    this    a good example to prove     you wrong

您将获得以下3个（或更多）结果：

% to proove you wrong %
% is %
% this % a good example % you %

如果您的算法为您选择了第二个结果，您会好吗？还是您会期望有所不同？所有3个均为有效结果。

但是您可能正在寻找最佳的，我们可以通过计算空格词来获得此值。

间隔词较少的结果是最好的。因此，您看到第二个是最坏的一个，而最后一个是最好的一个。但是要评估这一点，我们需要使用一种算法，该算法能够在第一步中找到所有结果，因此我们可以评估其中哪一个是最佳结果。