Functions/Get-LongestCommonSubsequence.ps1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function Get-LongestCommonSubsequence {
    <#
        .SYNOPSIS
            Get the longest common subsequence between two strings.
        .DESCRIPTION
            Get the longest common subsequence between two strings.
        .EXAMPLE
            Get-LongestCommonSubsequence -String1 'Pennsylvania' -String2 'pencilvaneya' -CaseSensitive
        .LINK
            https://gallery.technet.microsoft.com/scriptcenter/Longest-common-subsequence-173c0f45
            http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
            https://github.com/gravejester/Communary.PASM
        .NOTES
            Author: Barry Chum
    #>

    [CmdletBinding()]
    Param (
        [Parameter(Position = 0, Mandatory)]
        [ValidateNotNullorEmpty()]
        [string] $String1,

        [Parameter(Position = 1, Mandatory)]
        [ValidateNotNullorEmpty()]
        [string] $String2,

        [Parameter()]
        [switch] $CaseSensitive
    )

    if (-not($CaseSensitive)) {
        $String1 = $String1.ToLowerInvariant()
        $String2 = $String2.ToLowerInvariant()
    }

    $lengths = New-Object 'object[,]' ($String1.Length + 1), ($String2.Length + 1)

    for($i = 0; $i -lt $String1.length; $i++) {
      for ($j = 0; $j -lt $String2.length; $j++) {
        if ($String1[$i] -ceq $String2[$j]) {
          $lengths[($i+1),($j+1)] = $lengths[$i,$j] + 1
        } else {
          $lengths[($i+1),($j+1)] = [math]::max(($lengths[($i+1),$j]),($lengths[$i,($j+1)]))
        }
      }
    }

    $lcs = @()
    $x = $String1.length
    $y = $String2.length

    while (($x -ne 0) -and ($y -ne 0)) {
        if ( $lengths[$x,$y] -eq $lengths[($x-1),$y]) {
            --$x
        }
        elseif ($lengths[$x,$y] -eq $lengths[$x,($y-1)]) {
            --$y
        }
        else {
            if ($String1[($x-1)] -ceq $String2[($y-1)]) {
                $lcs = ,($String1[($x-1)]) + $lcs
            }
            --$x
            --$y
        }
    }
    Write-Output $lcs
}