Sparse Long Blocks and the Micro-Structure of the Longest Common Subsequences

S. Amsalu, C. Houdré, H. Matzinger

Consider two random strings having the same length and generated by an iid sequence taking its values uniformly in a fixed finite alphabet. Artificially place a long constant block…