Как вывести совпадающую часть двух строк, в то время как символ% отделяет непоследовательные части?

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

То, что вы пытаетесь сделать, нелегко, и вам потребуются некоторые продвинутые навыки разработки (базовые знания по динамическому программированию чрезвычайно полезны).

То, что вы пытаетесь сделать, на самом деле та же идея, что и выравнивание последовательностей ДНК в биоинформатике.

---

Итак, вам нужно взять обе строки (последовательности)

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?

Они могут быть выровнены (wordwise) как

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 возможных результатов.

Итак, вам нужен алгоритм, который может дать вам all возможных результатов, а затем вам нужен алгоритм, чтобы определить, какой из них является лучшим(тот, который вы хотите иметь). В вышеприведенном случае, как бы вы сказали, какой из двух результатов является правильным? … Вы не можете:)

---

Чтобы дать вам другой пример:

Мы используем следующие 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 являются действительными результатами.

Но вы, вероятно, ищете лучший, и мы можем получить это, посчитав пропущенные слова.

Результат с меньшим количеством слов является лучшим. Итак, вы видите, что второй - худший, а последний - лучший. Но чтобы оценить это, нам нужно использовать алгоритм, который может найти всех результатов на первом этапе, чтобы мы могли оценить, какой из них является лучшим.