Entrada:

Duas strings sem novas linhas ou espaços em branco.

Resultado:

Ambas as strings de entrada em linhas separadas, com espaços onde necessário ^† para uma das duas strings. E uma terceira linha com os caracteres A, R, Me , representando adicionados , removidos , modificados , e inalterada .

^† Adicionamos espaços à sequência de entrada superior ou inferior (se for necessário). O objetivo desse desafio é gerar a menor quantidade possível de alterações ( ARM), também conhecida como distância de Levenshtein .

Exemplo:

Digamos que as seqüências de entrada sejam ABCDEFe AFBECD, então a saída seria esta:

A B CDEF
AFBECD  
 A A  RR

Aqui estão algumas outras saídas inválidas possíveis, como exemplo (e há muito mais):

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

No entanto, nenhuma dessas mudanças possui apenas quatro alterações; portanto, apenas A B CDEF\nAFBECD \n A A RRuma saída válida para esse desafio.

Regras do desafio:

• Você pode assumir que as seqüências de entrada não conterão novas linhas ou espaços.
• As duas cadeias de entrada podem ter comprimentos diferentes.
• Uma das duas seqüências de entrada deve permanecer como está, exceto nos espaços iniciais / finais opcionais.
• Se seus idiomas não suportam nada além de ASCII, você pode assumir que a entrada conterá apenas caracteres ASCII imprimíveis.
• O formato de entrada e saída é flexível. Você pode ter três Strings separadas, uma matriz de String, uma única String com novas linhas, matriz de caracteres 2D, etc.
• Você tem permissão para usar outra coisa em vez de ARM, mas indique o que usou (ou seja 123, ou abc.etc.)
• Se mais de uma saída válida for possível com a mesma quantidade de alterações ( ARM), você poderá escolher se deseja gerar uma das saídas possíveis ou todas elas.

• Os espaços à esquerda e à direita são opcionais:

  A B CDEF
  AFBECD
   A A  RR
  

  ou

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

Regras gerais:

• Isso é código-golfe , então a resposta mais curta em bytes vence.
  Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para 'qualquer' linguagem de programação.
• As regras padrão se aplicam à sua resposta, para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados, programas completos. Sua chamada.
• As brechas padrão são proibidas.
• Se possível, adicione um link com um teste para o seu código.
• Além disso, adicione uma explicação, se necessário.

Casos de teste:

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 ¹ bytes

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

Experimente online! Exemplo de utilização: "ABCDEF" & "AFBECD". Retorna uma lista de três strings. Essa é uma extensão da minha solução recursiva à questão comum da distância de Levenshtein .

Explicação:

Para calcular as modificações mínimas para começar a partir "xyz"de "yw", vamos nos concentrar no primeiro caractere de ambas as cadeias. Existem três possibilidades:

• Remover: Gota xda primeira corda e recursivamente calcular as modificações para começar a partir "yz"de "yw". Isso produz as três linhas ["yz","yw"," M"]. Adicione xao primeiro, um espaço para o segundo e Rpara o terceiro. Nós temos

  xyz
  yw
  RM

• Adicionar: Solte yda segunda sequência e calcule "xyz" & "w", que retorna o resultado ["xyz","w","MRR"]. Precisamos adicionar um espaço na primeira linha, yna segunda eA na terceira linha:

   xyz
  yw
  AMRR

• Modificado / Inalterado: Podemos combinar esses dois casos, porque ambos precisam eliminar o primeiro caractere de ambas as seqüências e calcular as modificações mínimas entre as demais "yz" & "w". Para o resultado ["yz","w","MR"], adicionamos xele primeiro e yna segunda linha. Somente para a última linha, precisamos diferenciar se os caracteres iniciais são os mesmos. Se forem iguais, um espaço será adicionado à terceira linha, caso contrário (como neste caso, porque x \= y) umM é adicionado:

  xyz
  yw
  MMR

Desses três candidatos, precisamos encontrar o que tiver menos modificações. Isso é equivalente a ter mais espaços na terceira linha. Portanto, convertemos cada candidato s(uma lista de três cadeias) em uma tupla ([1|' '<-s!!2],s), onde saparece como segundo componente e o primeiro componente é uma lista com tantos elementos quanto espaços na terceira linha s( s!!2devido à indexação 0). Como o elemento list 1é usado, mas o elemento real é irrelevante, desde que seja o mesmo para todos os candidatos.

Ao todo, isso produz a lista de tuplas

[([1], ["xyz", "yw", "RM"])), ([], ["xyz", "yw", "AMRR"]), ([], ["xyz", " yw "," MMR "])]

_{¹ +15 bytes para corrigir um erro no qual A-changes no final de uma string seria exibido como R-changes}

JavaScript (ES6), 413 ... 343 342 bytes

Economizou 5 bytes ajustando os índices de loop, conforme sugerido por @KevinCruijssen

Recebe entrada como 2 strings na sintaxe de currying. Retorna uma matriz de 3 strings.

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]}

Casos de teste

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`);

Menos golfe

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
  ]
}

Exemplo

Abaixo está a matriz inicial para b = "foo" e a = "ok" :

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

e aqui está a matriz final após todas as iterações:

//                     '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'

A sequência final de modificação, juntamente com a distância de Levenshtein, são armazenadas na célula inferior direita.

Python 2 , 548 536 484 500 ¹ 488 447 381 ² 373 371 357 350 bytes

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

Experimente online!

Usa em 'ARM_'vez de'ARM '

Trabalha construindo a matriz de Levenshtein e depois retrocedendo para encontrar as operações . Agora cria a cadeia de operação ao mesmo tempo que a matriz de Levenshtein, como na resposta JS de Arnauld

_{1: Mais bytes, pois não funcionou se a primeira sequência fosse um único caractere.}

_{2: Mudou para construir as combinações na matriz de Levenshtein.}

Python 2 , 310 bytes

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])

Experimente online!

Usando difflib.SequenceMatcherisso calcula um alinhamento entre duas strings

Mathematica, 250 256 259 384 bytes

~ 0.00035 segundos para o caso do código 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})&

Uso: f["ABCDE", "ABCDF"]

Experimente online!

O código é baseado em um fato que SequenceAlignmentfunciona por padrão em

Com a configuração padrão SimilarityRules-> Automatic, cada correspondência entre dois elementos contribui com 1 para a pontuação total de similaridade, enquanto cada incompatibilidade, inserção ou exclusão contribui com -1.

Nomeadamente, a pontuação é calculada por M, Ae R, em conformidade.

Exemplo:

D , 351 345 bytes

-6 bytes thanx em KevinCruijssen

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;}

Experimente online!