Find a string in the middle

Question

Given two strings \$A\$ and \$B\$ with edit (Levenshtein) distance \$x\$, find a third string with edit distance \$a\$ to \$A\$ and edit distance \$b\$ to \$B\$ so that \$a+b=x\$ and \$a=int(x/2)\$ (that is half of \$x\$ rounded down to the nearest integer).

The input is the two strings \$A\$ and \$B\$ and their edit distance \$x\$. You don’t need to compute \$x\$.

\$A\$ is of length \$n\$ and \$B\$ is of length \$m\$ such that \$n/2 \le m \le n\$.

Your can take the input in any convenient format you like.

Examples

Inputs: "hello", "hallo", 1. Output: "hello"

Inputs: "sitteng", "kitten", 2. Output: "sitten"

Inputs: "bijamas", "banana", 4. Output: "banamas"

Inputs: "Pneumonoultramicroscopicsilicovolcanoconiosis", "noultramicroscopicsilicovolcanoconiosis", 6. Output: "umonoultramicroscopicsilicovolcanoconiosis"

Restriction

Your code must be run in \$O(n^2)\$ time where \$n\$ is the length of A.

Answer 1

Python, 459 514 502 bytes

+60 bytes, use correct initial condition
-11 bytes, thanks to ValueInk
-1 byte, thanks to c--

l=len
I=range
def f(s,t):
 m,n=l(s),l(t);w=m-~n;M=[[([t[:k]+s for k in I(j+1)],j)for j in I(n+1)]]+[[([s[k:]for k in I(i+2)],0)]+n*[0]for i in I(m)]
 for j in I(n):
  for i in I(m):D,d=M[i][j+1];U,u=M[i+1][j];R,r=M[i][j];a=l(D:=D+[p[:d]+p[d+1:]])if(p:=D[-1])[:d]==t[:d]else w;b=l(U:=U+[p[:u]+[t[j]]+p[u:]])if(p:=U[-1])[:u]==t[:u]else w;c=l(R:=R+[[],[p[:r]+[t[r]]+p[r+1:]]][p[r]!=t[r]])if(p:=R[-1])[:r]==t[:r]else w;M[i+1][j+1]={b:(U,u+1),c:(R,r+1),a:(D,d)}[min(a,b,c)]
 return(p:=M[m][n][0])[~-l(p)//2]

Attempt This Online!

Input&Output as lists of characters.

For some examples the result is different from the result in the question, but also satisfies the distance requirement

Explanation

Uses modified version of the dynamic programming algorithm for the computation of the Levenshtein distance. Each cell stores the current prefix length and the path of all previous edits. At the end the cell in the middle of the path is returned.

ungolfed code:

def levDist(s,t):
  m,n=len(s),len(t)
  w=m+n+1 # one larger than the largest possible Levenshtein distance
  M=[]
  # initialize first row and column
  for i in range(0, m+1):
    M.append([([s[k:] for k in range(i+1)],0)]+[0]*n)
  for j in range(1, n+1):
    M[0][j]=([t[:k]+s for k in range(j+1)],j)
  for j in range(0, n):
    for i in range(0, m):
      # cell i,j -> shortest edit path that:
      # 1) only modifies the first i characters in s 
      # 2) ends with a word starting with the first j characters in t 
      D,d=M[i][j+1] # deletion
      U,u=M[i+1][j] # insertion
      R,r=M[i][j]   # substitution
      # for each edit type check if the previous cell contains the correct prefix and if yes perform the repetitive edit
      if (p:=D[-1])[:d]==t[:d]:
        D=D+[p[:d]+p[d+1:]]
        a=len(D)
      else:
        a=w
      if (p:=U[-1])[:u]==t[:u]:
        U=U+[p[:u]+[t[j]]+p[u:]]
        b=len(U)
      else:
        b=w
      if (p:=R[-1])[:r]==t[:r]:
        if p[r]!=t[r]:
          R=R+[p[:r]+[t[r]]+p[r+1:]]
        c=len(R)
      else:
        c=w
      x=min(a,b,c) # find operation with the shortest edit path
      if x==a:
        M[i+1][j+1] = (D,d)
      elif x==b:
        M[i+1][j+1] = (U,u+1)
      else:
        M[i+1][j+1] = (R,r+1)
  return ((p:=M[m][n][0])[(len(p)-1)//2],M[m][n]) # the ungolfed version also returns the complete edit path

Attempt This Online!

Answer 2

Haskell, 182 175 bytes, not in \$O(n^2)\$

-7 bytes thanks to @Wheat Wizard

import Data.List
l=length
(x:w)#(y:z)|x==y=map(x:)$w#z
a@(x:w)#b|y:z<-b=sortOn l[a:w#b,a#z++[b],a:map(y:)(w#z)]!!0|1>0=a:w#[]
_#(y:z)=[]#z++[y:z]
_#_=[[]]
a%b=b#a!!div(l$b#a)2

Attempt This Online!

---

Edit: I remembered that the Levenshtein distance could be calculated in quadratic time, but I didn't remember which algorithm was the one with this time complexity and I didn't bother to check the complexity of the naive one.