Anonymous user
Longest common subsequence: Difference between revisions
+D
(Ada solution added) |
(+D) |
||
Line 111:
END IF
END FUNCTION</qbasic>
=={{header|D}}==
<d>module lcs ;
import std.stdio ;
T[] lcsr(T)(T[] a, T[] b) { // recursive
if(a.length == 0 || b.length == 0) return null ;
T[] x = b[0..$-1] , y = a[0..$-1] ;
if(a[$-1] == b[$-1]) { return lcsr(y, x) ~ a[$-1] ; }
x = lcsr(a, x) ; y = lcsr(y, b) ;
return x.length > y.length ? x : y ;
}
T imax(T)(T a, T b) { return a > b ? a : b ; }
T[] lcsi(T)(T[] a, T[] b) { // dynamic programming
int i,j, m = a.length , n = b.length ;
int[][] L = new int[][](m + 1,n + 1);
T[] res ;
for(i = 0 ; i < m ; i++)
for(j = 0 ; j < n ; j++)
L[i+1][j+1] = (a[i] == b[j]) ? 1 + L[i][j] : imax(L[i+1][j], L[i][j+1]) ;
while(i >0 && j >0)
if(a[i-1] == b[j-1]) {
res ~= a[i-1] ; i-- ; j-- ;
} else
if (L[i][j-1] < L[i-1][j])
i-- ;
else
j-- ;
return res.reverse ;
}
void main(string[] args) {
writefln(lcsr("thisisatest","testing123testing")) ;
writefln(lcsi("thisisatest","testing123testing")) ;
}</d>
=={{header|Haskell}}==
| |||