Help:=proc(): print(` PBE(u,v,P,P1,P2),F(m,n)`):
print(`BestMid(u,v,P,P1,P2)`):
end:




F:=proc(m,n) local a,b,i,j:
for j from 0 to n do
 a[j]:=1:
od:

for i from 1 to m do
  b[0]:=1:
   for j from 1 to n do
     b[j]:=b[j-1]+a[j]+a[j-1]:
   od:

 for j from 0 to n do
   a[j]:=b[j]:
 od:
od:
b[n]:
end:



#PBE(u,v,P,P1,P2)
#Price of best edit from word u to word v
#P is the matrix of replacement
#P1 is the list of insertion-costs
#P2 is the list of deletin-costs
PBE:=proc(u,v,P,P1,P2) local m,n,a,b,i,j:

m:=nops(u): n:=nops(v):

for j from 0 to n do
 a[j]:=0:
od:
 b[0]:=0:
for i from 1 to m do
  b[0]:=0:
   for j from 1 to n do
     b[j]:=max(b[j-1]+P1[v[j]], 
      a[j]+P2[v[j]] ,
       a[j-1]+P[u[i]][v[j]]  )
:
   od:

 for j from 0 to n do
   a[j]:=b[j]:
 od:
od:
b[n]:
end:


#BestMid(u,v,P,P1,P2): the coordinate i
#such that the best path goes through the point
#[m/2,i]
BestMid:=proc(u,v,P,P1,P2) local m,n,i,champ,rec,u1,v1,u1a,v1a,
cand,m1:
m:=nops(u): n:=nops(v):
m1:=trunc(m/2):
champ:=1:
rec:=0:

u1:=[op(1..m1,u)]:
u1a:=[op(m1+1..m,u)]:
u1a:=[seq(u1a[nops(u1a)-i],i=0..nops(u1a)-1)]:

for i from 2 to n do
 v1:=[op(1..i,v)]:
 v1a:=[op(i+1..n,v)]:

v1a:=[seq(v1a[nops(v1a)-j],j=0..nops(v1a)-1)]:
cand:=PBE(u1,v1,P,P1,P2)+PBE(u1a,v1a,P,P1,P2):

if cand>rec then
  rec:=cand:
  champ:=i:
fi:
od:

champ,rec:
end: