62 lines
1.8 KiB
D
62 lines
1.8 KiB
D
import std.stdio, std.algorithm, std.range, std.array, std.string, std.typecons;
|
|
|
|
uint[] lensLCS(R)(R xs, R ys) pure nothrow @safe {
|
|
auto prev = new typeof(return)(1 + ys.length);
|
|
auto curr = new typeof(return)(1 + ys.length);
|
|
|
|
foreach (immutable x; xs) {
|
|
swap(curr, prev);
|
|
size_t i = 0;
|
|
foreach (immutable y; ys) {
|
|
curr[i + 1] = (x == y) ? prev[i] + 1 : max(curr[i], prev[i + 1]);
|
|
i++;
|
|
}
|
|
}
|
|
|
|
return curr;
|
|
}
|
|
|
|
void calculateLCS(T)(in T[] xs, in T[] ys, bool[] xs_in_lcs,
|
|
in size_t idx=0) pure nothrow @safe {
|
|
immutable nx = xs.length;
|
|
immutable ny = ys.length;
|
|
|
|
if (nx == 0)
|
|
return;
|
|
|
|
if (nx == 1) {
|
|
if (ys.canFind(xs[0]))
|
|
xs_in_lcs[idx] = true;
|
|
} else {
|
|
immutable mid = nx / 2;
|
|
const xb = xs[0.. mid];
|
|
const xe = xs[mid .. $];
|
|
immutable ll_b = lensLCS(xb, ys);
|
|
|
|
const ll_e = lensLCS(xe.retro, ys.retro); // retro is slow with dmd.
|
|
|
|
//immutable k = iota(ny + 1)
|
|
// .reduce!(max!(j => ll_b[j] + ll_e[ny - j]));
|
|
immutable k = iota(ny + 1)
|
|
.minPos!((i, j) => tuple(ll_b[i] + ll_e[ny - i]) >
|
|
tuple(ll_b[j] + ll_e[ny - j]))[0];
|
|
|
|
calculateLCS(xb, ys[0 .. k], xs_in_lcs, idx);
|
|
calculateLCS(xe, ys[k .. $], xs_in_lcs, idx + mid);
|
|
}
|
|
}
|
|
|
|
const(T)[] lcs(T)(in T[] xs, in T[] ys) pure /*nothrow*/ @safe {
|
|
auto xs_in_lcs = new bool[xs.length];
|
|
calculateLCS(xs, ys, xs_in_lcs);
|
|
return zip(xs, xs_in_lcs).filter!q{ a[1] }.map!q{ a[0] }.array; // Not nothrow.
|
|
}
|
|
|
|
string lcsString(in string s1, in string s2) pure /*nothrow*/ @safe {
|
|
return lcs(s1.representation, s2.representation).assumeUTF;
|
|
}
|
|
|
|
void main() {
|
|
lcsString("thisisatest", "testing123testing").writeln;
|
|
}
|