Longest Common Subsequence and Longest Subsequence Palindrome

The following code computes:

• The longest common subsequence between two strings, where a subsequence of a sequence does not have to consist of contiguous elements of the sequence.

• The longest subsequence in a string that is a palindrome.

All suggestions are welcome (more idiomatic f#, optimizations, styling, etc..).

let stringReverse (s: string) = 
    System.String(Array.rev (s.ToCharArray()))

//assumes you don't go above the high bound of the indices
let SafeIndex (arr: int [,]) (i: int) (j: int) : int =
    if i = 0 && j >= 0 do
        let NW = SafeIndex c (i - 1) (j - 1)
        let N = SafeIndex c (i - 1) j
        let W = SafeIndex c i (j - 1)

        if N > NW && i > 0 then
            i  NW && j > 0 then
            j  0)

    for i in 0 .. x.Length - 1 do
        for j in 0 .. y.Length - 1 do
            if x.[i] = y.[j] then
                c.[i, j]  0)

    for i in 0 .. x.Length - 1 do
        c.[i, i]  c.[i, j - 1] then
        i ]
let main argv = 
    let x = "agbfcecebfag"
    let y = "gafbececfbga"
    let char = "character"

    let c = LCS x y
    printfn "%A" c
    printfn "%s" (ConstructLCS c x y)

    let d = LSPalindrome x
    printfn "%A" d
    printfn "%s" (ConstructLSPalindrome d x)

    let e = LSPalindrome char
    printfn "%A" e
    printfn "%s" (ConstructLSPalindrome e char)

    0

The output follows:

```
[[0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1]
[1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2; 2]
[1; 1; 1; 2; 2; 2; 2; 2; 2; 2; 2; 2]
[1; 1; 2; 2; 2; 2; 2; 2; 3; 3; 3; 3]
[1; 1; 2; 2; 2; 3; 3; 3; 3; 3; 3; 3]
[1; 1; 2; 2; 3; 3; 4; 4; 4; 4; 4; 4]
[1; 1; 2; 2; 3; 4; 4; 5; 5; 5; 5; 5]
[1; 1; 2; 2; 3; 4; 5; 5; 5; 5; 5; 5]
[1; 1; 2; 3; 3; 4; 5; 5; 5; 6; 6; 6]
[1; 1; 2; 3; 3; 4; 5; 5; 6; 6; 6; 6]
[1; 2; 2; 3; 3; 4; 5; 5; 6; 6; 6; 7]
[1; 2; 2; 3; 3; 4; 5; 5; 6; 6; 7; 7]]
abcecba
[[1; 1; 1; 1; 1; 1; 3; 3; 5; 5; 7; 7]
[0; 1; 1; 1; 1; 1; 3; 3; 5; 5; 5; 7]
[0; 0; 1; 1; 1; 1; 3; 3; 5; 5; 5; 5]
[0; 0; 0; 1; 1; 1; 3; 3; 3; 5; 5; 5]
[0

Overall the code is written in a more procedural style rather than a functional style. By which I mean it would be relatively straightforward to port it to an imperative language such as C, Pascal, Python or Basic. There's nothing wrong with that in many cases, and that's why F# provides tools for writing code in a procedural manner.

A few comments:

-
What is in a Name: What do N, W and NW mean? What exactly do i and j index?

-
Names 2: What does LCS stand for? Sure with the title of the question, I can make an educated guess. But in the middle of 400 lines of code a call to ConstructLCS() could mean just about anything.

-
Names 3: Finding is the level of abstraction I need when I call this as a library function. Construct tells me how the process is finding the LongestCommonSubstring.

-
Functional Style 1: Pattern matching rather than nested ifs, see "Variable Matching" here. This pure syntactic sugar is what makes functional programs read like functional programs.

-
Functional Style 2: Recursive tail-calls versus loops. Again it's syntactic sugar and tail-call optimization is literally the compiler unrolling recursion into loops. But it eliminates the declaration of mutable indices from the source code. To paraphrase Rich Hickey, we don't really want to change variables, we just want the next values for the parameter we are passing to our function.

StackExchange Code Review Q#66818, answer score: 3