Блог

Существует ли существующий алгоритм, чтобы сделать что-то подобное, из нескольких результатов воссоздать исходную строку формата.

Например, вот входные:

 "the fox jumps over the lazy brown dog"
"the man jumps over the lazy black cat"
"the dolphin jumps over the big wave"
 

=> вывод:

 output="the {} jumps over the {}"
 

Существует несколько строк формата, которые работают, но мы должны получить строку с наибольшим количеством символов, которые не принадлежат владельцам мест, и наименьшим количеством владельцев мест.

поскольку в python мы имеем:

 "the fox jumps over the lazy brown dog" = output.format('fox', 'lazy brown dog')
"the man jumps over the lazy black cat" = output.format('man ', 'lazy black cat')
"the dolphin jumps over the big wave" = output.format('dolphin', 'big wave')
 

или даже лучше на C, предполагая, что при достаточном количестве входных данных мы можем получить

 output = "the %s jumps over the %s"
 

Насколько мне известно, в стандартных библиотеках такого алгоритма нет. Мы можем рассматривать это как вариант проблемы с самой длинной общей подстрокой, вот идея о том, как это сделать.

Наивный алгоритм был бы примерно таким:

 1. Split the first string, with ' ' (space) as split character and keep this array
   (base_array)

2. For each following input :
    a. Split string with ' ' as split character, let's call this array curr_array

    b. Compare, from left to right, each curr_array entry with the base_array entries and 
       apply the following rule: 
         - match at curr_array[i] and base_array[j]:
               compare curr_array[i 1] and base_array[j 1]

         - no match at curr_array[i] and base_array[j]:
               recurse b. with curr_array[i 1] and base_array[j], if recursion found a
               match at curr_array[i k], continue algorithm from the top of the recursion
               from curr_array[i k 1] and base_array[j 1],

               if recursion was not successful update base_array[j] = "" and continue
               algorithm with curr_array[i] and base_array[j 1]
 

Допустим, у вас есть два входа:

 "this is a very poor and long example"
"this is a good and short example"
 

Когда алгоритм завершится, base_array будет содержать записи, подобные этой:

 [this][is][a][][][and][][example]
 

Затем просто перегруппируйте соседние пустые записи:

 [this][is][a][][and][][example]
 

Замените оставшиеся пустые записи символами по вашему выбору и присоединитесь к списку, чтобы получить желаемый результат

 this is a {} and {} example
 

Надеюсь, это помогло!