--- a/julia/dp.jl	Thu Mar 02 23:06:32 2023 +0100
+++ b/julia/dp.jl	Fri Mar 03 00:23:39 2023 +0100
@@ -402,3 +402,113 @@
 
     min(xfirst, yfirst)
 end
+
+function shortest_common_supersequence_track_s(x::AbstractString, y::AbstractString)::String
+    byL = fill(' ', length(x)+length(y))
+    L = shortest_common_supersequence_track(x, y, 1, 1, 0, [length(x)+length(y)], byL)
+    String(byL[1:L])
+end
+
+function shortest_common_supersequence_track(x::AbstractString, y::AbstractString, i=1, j=1, L=0, Lmin=[length(x)+length(y)], byL=fill(' ', length(x)+length(y)), mem=Dict{Tuple,Int}())::Int
+    if (i, j, L) in keys(mem)
+        return mem[(i,j,L)]
+    end
+    if i > length(x) || j > length(y)
+        L_ = max(length(y)-j+1, length(x)-i+1)
+        Lmin[1] = min(Lmin[1], L_ + L)
+        if i > length(x)
+            byL[L+1:L+L_] .= collect(y[j:end])
+        else
+            byL[L+1:L+L_] .= collect(x[i:end])
+        end
+        mem[(i, j, L)] = L_+L
+        return L_ + L
+    end
+
+    # Case 1: current first letters identical
+    if x[i] == y[j]
+        L_ = shortest_common_supersequence_track(x, y, i+1, j+1, L+1, Lmin, byL, mem)
+        if L_ == Lmin[1]
+            byL[L+1] = x[i]
+        end
+        mem[(i, j, L)] = L_
+        return L_
+    end
+
+    # Case 2: current first letters are not identical: choose shortest supersequence from here.
+
+    # take from x
+    xfirst = shortest_common_supersequence_track(x, y, i+1, j, L+1, Lmin, byL, mem)
+    # take from y
+    yfirst = shortest_common_supersequence_track(x, y, i, j+1, L+1, Lmin, byL, mem)
+
+    if xfirst < yfirst
+        if xfirst == Lmin[1]
+            byL[L+1] = x[i]
+        end
+    else
+        if yfirst == Lmin[1]
+            byL[L+1] = y[j]
+        end
+    end
+
+    R = min(xfirst, yfirst)
+    mem[(i,j,L)] = R
+    R
+end
+
+function longest_palindromic_subsequence(s::AbstractVector, i=1, j=length(s))::Int
+    if i > j
+        return 0
+    elseif i == j
+        return 1
+    else
+        if s[i] == s[j]
+            2 + longest_palindromic_subsequence(s, i+1, j-1)
+        else
+            right = longest_palindromic_subsequence(s, i, j-1)
+            left = longest_palindromic_subsequence(s, i+1, j)
+            max(left, right)
+        end
+    end
+end
+
+function longest_palindromic_subsequence_tracking_s(s::AbstractVector{T})::Vector where {T}
+    byL = zeros(T, length(s))
+    l = longest_palindromic_subsequence_tracking(s, 1, length(s), 0, [0], byL)
+    byL
+end
+
+"""As above, but tracks longest sequence. Note: palindromic length defined here as 1 + length of a half.
+"""
+function longest_palindromic_subsequence_tracking(s::AbstractVector{T}, i=1, j=length(s), L=0, Lmax=[0], byL=zeros(T, length(s)), mem=Dict{Tuple,Int}())::Int where {T}
+    if (i,j,L) in keys(mem)
+        return mem[(i,j,L)]
+    end
+
+    if i > j
+        return 0
+    elseif i == j
+        if L+1 > Lmax[1]
+            Lmax[1] = L+1
+            byL[L+1] = s[i]
+        end
+        mem[(i,j,L)] = 1 + L
+        return 1 + L
+    else
+        if s[i] == s[j]
+            L_ = longest_palindromic_subsequence_tracking(s, i+1, j-1, L+1, Lmax, byL, mem)
+            if L_ == Lmax[1]
+                byL[L+1] = s[i]
+            end
+            mem[(i, j, L)] = L_
+            return L_
+        else
+            right = longest_palindromic_subsequence_tracking(s, i, j-1, L, Lmax, byL, mem)
+            left = longest_palindromic_subsequence_tracking(s, i+1, j, L, Lmax, byL, mem)
+            m = max(left, right)
+            mem[(i,j,L)] = m
+            m
+        end
+    end
+end