longest common subsequence code in chapel language.

lcs.chpl

proc lcsDPTable(str1: string, str2: string) {
    // writeln(str1, " ", str2);
    var dpTable: [1..str1.size+1, 1..str2.size+1] int, i, j: int;
    const n = str1.size;
    const m = str2.size;
    var lcs: string;
    for i in 1..n {
        for j in 1..m {
            if str1[i] == str2[j] {
                dpTable[i+1, j+1] = dpTable[i, j] + 1;
            } else {
                dpTable[i+1, j+1] = max(dpTable[i+1, j], dpTable[i, j+1]);
            }
        }
    }
    return dpTable;
}

proc lcsTrim(str1: string, str2: string) {
    var n = str1.size;
    var m = str2.size;
    var start = 1;
    var endRemove = 0, startRemove = 0;
    while start <= n  && start <= m && str1[start] == str2[start] {
        start += 1;
        startRemove += 1;
    }
    while start <= n  && start <= m && str1[n] == str2[m] {
        n -= 1;
        m -= 1;
        endRemove += 1;
    }
    return [startRemove, endRemove];
}

proc lcsLength(in str1: string, in str2: string): int {
    var trimIndexes = lcsTrim(str1, str2);
    // writeln(str1, " ", str2, " ", trimIndexes);
    var  n = str1.size+1;
    var  m = str2.size+1;
    str1 = str1[1+trimIndexes[1]..n-1-trimIndexes[2]];
    str2 = str2[1+trimIndexes[1]..m-1-trimIndexes[2]];
    n = str1.size+1;
    m = str2.size+1;
    return lcsDPTable(str1, str2)[str1.size+1, str2.size+1] + trimIndexes[1] + trimIndexes[2];
}

proc lcs(in str1: string, in str2: string): string {
    var trimIndexes = lcsTrim(str1, str2);
    // writeln(str1, " ", str2, " ", trimIndexes);
    var  n = str1.size+1;
    var  m = str2.size+1;
    var  i=n, j=m;
    var prefix="", suffix="";

    if(trimIndexes[1]) {
        prefix = str1[1..trimIndexes[1]];
    }
    if(trimIndexes[2]) {
        suffix = str1[n-trimIndexes[2]..n-1];
    }
    str1 = str1[1+trimIndexes[1]..n-1-trimIndexes[2]];
    str2 = str2[1+trimIndexes[1]..m-1-trimIndexes[2]];
    // writeln(prefix);
    // writeln(suffix);
    // writeln(str1, " ", str2);
    
    var dpTable = lcsDPTable(str1, str2);
    n = str1.size+1;
    m = str2.size+1;
    i=n; j=m;
    var lcsString = "";
    while i!=1 && j!=1 {
        if dpTable[i, j] == dpTable[i-1, j] {
            i -= 1;
        }
        else if  dpTable[i, j] == dpTable[i, j-1] {
            j -= 1;
        }
        else {
            lcsString = str1[i-1] + lcsString;
            i -= 1;
            j -= 1;
        }
        
    }
    return prefix + lcsString + suffix;
}



// Tests
writeln(lcs('1234', '1224533324'), " ", lcs('abcda', 'bdabac')); // 1234, abc
writeln(lcs('thisisatest', 'testing123testing'), " ", lcs('classical', 'musical')); // tsitest, sical
writeln(lcs('hisisatest', 'testing123testing'), " ", lcs('cla', 'mu')); // sitest, 

writeln(lcsLength('1234', '1224533324'), " ", lcsLength('abcda', 'bdabac')); // 4, 3
writeln(lcsLength('thisisatest', 'testing123testing'), " ", lcsLength('classical', 'musical')); // 7, 5
writeln(lcsLength('hisisatest', 'testing123testing'), " ", lcsLength('cla', 'mu')); // 6, 0