Входные данные:

Две строки без перевода строки или пробелов.

Выход:

Обе входные строки в отдельных строках с пробелами, где это необходимо ^† для одной из двух строк. И третья строка с символами A, R, Mи , представляющий собой добавлена , удалена , изменена , и без изменений .

^† Мы добавляем пробелы в верхнюю или нижнюю строку ввода (если нужно). Цель этой задачи - вывести с наименьшим количеством возможных изменений ( ARM), также известных как расстояние Левенштейна .

Пример:

Допустим, входные строки имеют вид ABCDEFи AFBECD, тогда результат будет таким:

A B CDEF
AFBECD  
 A A  RR

Вот несколько других возможных неправильных выводов в качестве примера (и их намного больше):

ABCDEF
AFBECD
 MMMMM

A BCDEF
AFBECD 
 A MMMR

AB CDEF
AFBECD 
 MAMMMR

ABC DEF
AFBECD 
 MMAMMR

ABC  DEF
AFBECD  
 MMAA RR

ABCDEF 
AFB ECD
 MMR MA

 AB CDEF   // This doesn't make much sense,
AFBECD     // but it's to show leading spaces are also allowed
AM A  RR

Однако ни одно из них не имеет только четырех изменений, поэтому только A B CDEF\nAFBECD \n A A RRдопустимый результат для этой задачи.

Правила соревнований:

• Вы можете предположить, что входные строки не будут содержать никаких новых строк или пробелов.
• Две входные строки могут быть разной длины.
• Одна из двух входных строк должна оставаться как есть, за исключением необязательных начальных / конечных пробелов.
• Если ваши языки не поддерживают ничего кроме ASCII, вы можете предположить, что ввод будет содержать только печатные символы ASCII.
• Формат ввода и вывода являются гибкими. Вы можете иметь три отдельных строки, массив строк, одну строку с новыми строками, двумерный массив символов и т. Д.
• Вам разрешено использовать что-то другое вместо ARM, но указать, что вы использовали (то есть 123, или abc., и т. Д.)
• Если с одним и тем же количеством изменений возможны несколько допустимых выходных данных ( ARM), вы можете выбрать, выводить ли один из возможных выходных данных или все из них.

• Начальные и конечные пробелы являются необязательными:

  A B CDEF
  AFBECD
   A A  RR
  

  или

  "A B CDEF\nAFBECD\n A A  RR"
                   ^
                   Note there are no spaces here
  

Основные правила:

• Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
  Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте придумать как можно более короткий ответ для «любого» языка программирования.
• К вашему ответу применяются стандартные правила , поэтому вы можете использовать STDIN / STDOUT, функции / метод с правильными параметрами, полные программы. Ваш звонок.
• По умолчанию лазейки запрещены.
• Если возможно, добавьте ссылку с тестом для вашего кода.
• Также, пожалуйста, добавьте объяснение, если это необходимо.

Тестовые случаи:

In: "ABCDEF" & "AFBECD"

Output (4 changes):
A B CDEF
AFBECD  
 A A  RR                  

In: "This_is_an_example_text" & "This_is_a_test_as_example"

Possible output (13 changes):
This_is_an       _example_text
This_is_a_test_as_example     
         MAAAAAAA        RRRRR

In: "AaAaABBbBBcCcCc" & "abcABCabcABC"

Possible output (10 changes):
AaAaABBbBBcCcCc
 abcABCab cABC 
R MM  MMMR MM R

In: "intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}" & "intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}"

Possible output (60 changes):
intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}
intf(){i ntr=(      i    n      t)(M  ath.r   andom        ()*         10          );returnr>0?r%2:2;}
       MR M  MRRRRRR RRRR RRRRRR MMMRR MMMMRRR     RRRRRRRR  MRRRRRRRRR  RRRRRRRRRR 

In: "ABCDEF" & "XABCDF"

Output (2 changes):
 ABCDEF
XABCD F 
A    R 

In: "abC" & "ABC"

Output (2 changes):
abC
ABC
MM 

Haskell , 192 181 174 161 158 150 147 143 158 ¹ байт

e@(a:r)&f@(b:s)=snd$maximum[([1|' '<-s!!2],s)|s<-z(z(:))[a:" R",' ':b:"A",a:b:last("M":[" "|a==b])][r&f,e&s,r&s]]
x&y=[x,y,"RA"!!(0^length x)<$x++y]
z=zipWith

Попробуйте онлайн! Пример использования: "ABCDEF" & "AFBECD". Возвращает список из трех строк. Это продолжение моего рекурсивного решения обычного вопроса о расстоянии Левенштейна .

Объяснение:

Для того, чтобы вычислить минимальные изменения , чтобы получить от "xyz"к "yw", мы ориентируемся на первый символ обеих строк. Есть три варианта:

• Удалить: Капля xиз первой строки и рекурсивно вычислить изменения , чтобы получить от "yz"до "yw". Это дает три строки ["yz","yw"," M"]. Добавьте xк первому, пробел ко второму и Rк третьему. Мы получаем

  хуг
  уш
  RM

• Добавить: Удалить yиз второй строки и вычислить "xyz" & "w", что возвращает результат ["xyz","w","MRR"]. Нам нужно добавить пробел в первой строке, yво второй и Aтретьей строке:

   хуг
  уш
  AMRR

• Модифицированный / Без изменений: Мы можем объединить эти два случая , потому что оба требуют , чтобы отбросить первый символ обеих строк и вычислить минимальные изменения между остальными строками: "yz" & "w". К результату ["yz","w","MR"]добавляем xон первую и yвторую строку. Только для последней строки мы должны различать, являются ли начальные символы одинаковыми. Если они одинаковы, к третьей строке добавляется пробел, в противном случае (как в этом случае, потому что x \= y) Mдобавляется an :

  хуг
  уш
  MMR

Из этих трех кандидатов нам нужно найти того, у кого меньше модификаций. Это эквивалентно наличию наибольшего количества пробелов в третьей строке. Поэтому мы преобразуем каждого кандидата s(список из трех строк) в кортеж ([1|' '<-s!!2],s), где он sотображается как второй компонент, а первый компонент представляет собой список с таким количеством элементов, сколько имеется пробелов в третьей строке s( s!!2из-за индексации 0). В качестве элемента списка 1используется, но фактический элемент не имеет значения, если он одинаков для всех кандидатов.

В целом, это дает список кортежей

[([1], ["xyz", "yw", "RM"]), ([], ["xyz", "yw", "AMRR"]), ([], ["xyz", " уш», "КМС"])]

_{¹ + 15 байт, чтобы исправить ошибку, при которой A-changes в конце строки будет отображаться как R-changes}

JavaScript (ES6), 413 ... 343 342 байта

Экономия 5 байтов путем настройки индексов цикла, как это было предложено @KevinCruijssen

Принимает ввод как 2 строки в синтаксисе карри. Возвращает массив из 3 строк.

b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

Контрольные примеры

let f =

b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

console.log(f('ABCDEF')('AFBECD').join`\n`);
console.log(f('This_is_an       _example_text')('This_is_a_test_as_example').join`\n`);
console.log(f('AaAaABBbBBcCcCc')('abcABCabcABC').join`\n`);
console.log(f("intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}")("intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}").join`\n`);
console.log(f('ABCDEF')('XABCDF').join`\n`);

Меньше гольфа

b => a => {
  m = []; x = a.length; y = b.length;

  // initialize the leftmost column and the topmost row
  for(i = j = 0, c = d = ''; i <= y; c += R = 'R')
    m[i] = [[c, i++]];
  for(; j++ < x;)
    m[i = 0][j] = [d += A = 'A', j];

  // walk through the Levenshtein matrix
  for(; i < y; i++)
    for(j = 0; j < x;)
      [C] = m[                                // C = current string, once updated
        [X, S] = m[i][j],                     // substitution
        [Y, I] = m[i + 1][j],                 // insertion
        [Z, D] = m[i][++j],                   // deletion
        Q = [Z + R, D + 1],                   // precomputed update for deletion
        i + 1
      ][j] =
        b[i] == a[j - 1] ?
          [X + ' ', S]                        // unchanged character
        :
          S < I ?
            D < S ? Q : [X + 'M', S + 1]      // deletion or substitution
          :
            D < I ? Q : [Y + A, I + 1];       // deletion or insertion

  return [
    // g = helper function to format the output strings by inserting spaces
    (g = s => C.replace(/./g, c => c == s ? ' ' : b[i++], i = 0))(A),
    g(R, b = a),

    // final modification string, picked from the last visited cell
    C
  ]
}

пример

Ниже приведена исходная матрица для b = "foo" и a = "ok" :

//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ],  (undefined),  (undefined) ],  // 'f'
  [ [ 'RR',  2 ],  (undefined),  (undefined) ],  // 'o'
  [ [ 'RRR', 3 ],  (undefined),  (undefined) ] ] // 'o'

и вот окончательная матрица после всех итераций:

//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ], [ 'M',   1 ], [ 'MA',  2 ] ],  // 'f'
  [ [ 'RR',  2 ], [ 'R ',  1 ], [ 'R A', 2 ] ],  // 'o'
  [ [ 'RRR', 3 ], [ 'RR ', 2 ], [ 'R M', 2 ] ] ] // 'o'

Последняя строка модификации вместе с расстоянием Левенштейна хранятся в правой нижней ячейке.

Python 2 , 548 536 484 500 ¹ 488 447 381 ² 373 371 357 350 байт

s,t=input()
n,m=len(s),len(t)
r=range
L=[[(j,'RA'[i<1]*j)for j in r(i,m-~i)]for i in r(n+1)]
for i in r(n):
 for j in r(m):M,R=L[i][j:j+2];A=L[i+1][j];v,V=min(A,R,M);x=('AR'[v in R],'M_'[s[i]==t[j]])[v in M];_=M;X=eval(x)[1]+x;L[i+1][j+1]=v+(x<'_'),X
for i in r(len(X)):s=s[:i]+' '*('B'>X[i])+s[i:];t=t[:i]+' '*('R'==X[i])+t[i:]
print s+'\n'+t+'\n'+X

Попробуйте онлайн!

Использует 'ARM_'вместо'ARM '

Работает, выстраивая матрицу Левенштейна, а затем возвращаясь назад, чтобы найти операции . Теперь строит строку операции одновременно с матрицей Левенштейна, как в ответе Арно на JS

_{1: Больше байтов, так как это не сработало, если первая строка была одним символом.}

_{2: перешел на построение комбинаций в матрице Левенштейна.}

Python 2 , 310 байт

from difflib import*
a,b=input()
U,j=[],' '
for g,s,t,x,y in SequenceMatcher(0,a,b).get_opcodes():
	g,Y,T=g[0],y-x,t-s
	z,A,B=Y-T,a[s:t],b[x:y]
	if'q'<g:U+=[A+z*j,B+j*-z,'M'*min(T,Y)+'A'*z+'R'*-z]
	if'e'==g:U+=[A,B,j*Y]
	if'i'==g:U+=[j*Y,B,'A'*Y]
	if'e'>g:U+=[A,j*T,'R'*T]
for e in[0,1,2]:print''.join(U[e::3])

Попробуйте онлайн!

Используя difflib.SequenceMatcherэто вычисляет выравнивание между двумя строками

Математика, 250 256 259 384 байтов

~ 0,00035 секунд для случая кода Java.

(i=o=p="";a=Array;r=StringLength;If[Length@#>0,g=#&@@#;h=#[[2]];u=r@g;v=r@h;i=i<>g;o=o<>h;w=Abs[v-u];k=a[" "&,w];If[u<v,i=i<>k,o=o<>k];p=p<>a["M"&,u~Min~v];p=p<>a[If[u>v,"R","A"]&,w],i=i<>#;o=o<>#;p=p<>a[" "&,r@#]]&/@SequenceAlignment[#,#2];{i,o,p})&

Использование: f["ABCDE", "ABCDF"]

Попробуйте онлайн!

Код основан на том факте, что SequenceAlignmentпо умолчанию работает на

При настройке по умолчанию SimilarityRules-> Automatic каждое совпадение между двумя элементами добавляет 1 к общему баллу сходства, а каждое несоответствие, вставка или удаление - -1.

А именно, скоринг рассчитывается M, Aи R, соответственно.

Пример:

D , 351 345 байт

-6 байт спасибо Кевину Круйссену

string f(string a,string b){import std.algorithm;string x,y,z;size_t i,j,k;foreach(c;levenshteinDistanceAndPath(a,b)[1]){final switch(c)with(EditOp){case none:x~=a[i++];y~=b[j++];z~=" ";break;case substitute:x~=a[i++];y~=b[j++];z~="M";break;case insert:x~=" ";y~=b[j++];z~="A";break;case remove:x~=a[i++];y~=" ";z~="R";}}return x~"\n"~y~"\n"~z;}

Попробуйте онлайн!