"""Owned full edit table, deterministic traceback and executable in-place edit script."""
import json
def align(s,t):
    n,m=len(s),len(t);d=[[0]*(m+1)for _ in range(n+1)];back={}
    for i in range(1,n+1):d[i][0]=i;back[i,0]=('delete',i-1,0)
    for j in range(1,m+1):d[0][j]=j;back[0,j]=('insert',0,j-1)
    for i in range(1,n+1):
        for j in range(1,m+1):
            same=s[i-1]==t[j-1]
            choices=[(d[i-1][j-1]+int(not same),'keep'if same else'replace',i-1,j-1),(d[i-1][j]+1,'delete',i-1,j),(d[i][j-1]+1,'insert',i,j-1)]
            value,op,a,b=min(choices,key=lambda x:x[0]);d[i][j]=value;back[i,j]=(op,a,b)
    i,j=n,m;ops=[]
    while i or j:
        op,a,b=back[i,j];ops.append({'operation':op,'source_prefix_from':a,'target_prefix_from':b,'read':s[a]if op!='insert'else None,'write':t[b]if op!='delete'else None});i,j=a,b
    ops.reverse();working=list(s);cursor=0;stages=[]
    for row in ops:
        op=row['operation']
        if op!='insert':assert cursor<len(working)and working[cursor]==row['read']
        if op=='keep':cursor+=1
        elif op=='replace':working[cursor]=row['write'];cursor+=1
        elif op=='delete':working.pop(cursor)
        else:working.insert(cursor,row['write']);cursor+=1
        stages.append({**row,'cursor_after':cursor,'working_text_after':''.join(working)})
    assert ''.join(working)==t and cursor==len(t)and sum(x['operation']!='keep'for x in ops)==d[n][m]
    return {'source':s,'target':t,'distance':d[n][m],'complete_dp_table':d,'tie_policy':'diagonal keep/replace, then delete, then insert','traceback_and_executed_stages':stages,'reconstructed':''.join(working)}
def enumerate_alignments(s,t):
    costs=[]
    def visit(i,j,cost):
        if i==len(s)and j==len(t):costs.append(cost);return
        if i<len(s)and j<len(t):visit(i+1,j+1,cost+int(s[i]!=t[j]))
        if i<len(s):visit(i+1,j,cost+1)
        if j<len(t):visit(i,j+1,cost+1)
    visit(0,0,0);best=min(costs);return {'all_alignment_paths':len(costs),'minimum_cost':best,'optimal_alignment_paths':costs.count(best)}
def demo():
    cases=[]
    for s,t in [('سارا','باران'),('ABCD','BCE'),('ab','ba'),('','آب')]:
        r=align(s,t);oracle=enumerate_alignments(s,t);assert r['distance']==oracle['minimum_cost']==2;cases.append({'alignment':r,'independent_all_alignment_paths':oracle})
    assert [x['operation']for x in cases[2]['alignment']['traceback_and_executed_stages']]==['replace','replace']
    assert cases[2]['independent_all_alignment_paths']['optimal_alignment_paths']==3
    assert align('ی','ی')['distance']==0 and align('ی','ي')['distance']==1
    assert align('ab','ba')['distance']==2 # No unit-cost transposition operation.
    return {'unit':'Unicode code points; no normalization, grapheme segmentation or transposition operation','authored_cases':cases,'raw_arabic_persian_yeh_different':True,'speech_model_or_semantic_correctness_executed':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=False,indent=2))