Edit Distance Yet Again#11099
ЦЕ КАПЕЦЬ
user197739 import sys
def match_len(s, t, i, j, n, m):c = 0while i < n and j < m and s[i] == t[j]:i += 1; j += 1; c += 1return c
NEG = -1
def solve(s, t, n, m, k):if abs(n - m) > k:return Nonetarget_d = m - n
dp = []
l0 = match_len(s, t, 0, 0, n, m)
dp.append([l0])
found_D = 0 if (target_d == 0 and l0 == n) else None
if found_D is None:
for e in range(1, k + 1):
prev = dp[e - 1]
pe = e - 1
cur = [NEG] * (2 * e + 1)
for d in range(-e, e + 1):
best = NEG
if -pe <= d <= pe:
v = prev[d + pe]
if v != NEG and v + 1 > best:
best = v + 1
if -pe <= d - 1 <= pe:
v = prev[(d - 1) + pe]
if v != NEG and v > best:
best = v
if -pe <= d + 1 <= pe:
v = prev[(d + 1) + pe]
if v != NEG and v + 1 > best:
best = v + 1
if best == NEG:
continue
i0 = best
if i0 < 0 or i0 > n:
continue
j0 = i0 + d
if j0 < 0 or j0 > m:
continue
i0 += match_len(s, t, i0, j0, n, m)
cur[d + e] = i0
dp.append(cur)
if -e <= target_d <= e and cur[target_d + e] == n:
found_D = e
break
if found_D is None:
return None
D = found_D
moves = []
e = D
d = target_d
while e > 0:
prev = dp[e - 1]
pe = e - 1
subst = NEG
if -pe <= d <= pe:
v = prev[d + pe]
if v != NEG:
subst = v + 1
ins = NEG
if -pe <= d - 1 <= pe:
v = prev[(d - 1) + pe]
if v != NEG:
ins = v
dele = NEG
if -pe <= d + 1 <= pe:
v = prev[(d + 1) + pe]
if v != NEG:
dele = v + 1
i_move = max(subst, ins, dele)
if subst == i_move:
i0 = i_move - 1
j0 = i0 + d
moves.append(('R', i0, j0))
elif ins == i_move:
i0 = i_move
j0 = i0 + (d - 1)
moves.append(('I', i0, j0))
d = d - 1
else:
i0 = i_move - 1
j0 = i0 + (d + 1)
moves.append(('D', i0, j0))
d = d + 1
e -= 1
moves.reverse()
ops = []
pos = 1
prev_i = 0
for (typ, i0, j0) in moves:
pos += (i0 - prev_i)
if typ == 'R':
ops.append("REPLACE %d %s" % (pos, t[j0]))
pos += 1
prev_i = i0 + 1
elif typ == 'I':
ops.append("INSERT %d %s" % (pos, t[j0]))
pos += 1
prev_i = i0
else:
ops.append("DELETE %d" % pos)
prev_i = i0 + 1
return opsdef main():data = sys.stdin.buffer.read().split()idx = 0z = int(data[idx]); idx += 1out = []for _ in range(z):n = int(data[idx]); m = int(data[idx+1]); k = int(data[idx+2])idx += 3s = data[idx].decode(); idx += 1t = data[idx].decode(); idx += 1res = solve(s, t, n, m, k)if res is None:out.append("NO")else:out.append("YES")out.append(str(len(res)))out.extend(res)sys.stdout.write("\n".join(out) + "\n")
if name == "main":main()