Scribd
Upload
4K views

Algorithm Design Solutions

This document proves that the length of the shortest string that can be constructed as a concatenation of strings from two sets A and B, each containing at most n strings of maximum length L, is at most n^2L^2. It argues that if a string u of length greater than n^2L^2 could be constructed, the pigeonhole principle would imply two positions p and p' in u have the same type, and the substring between p and p' could be removed, contradicting u's minimality.

Uploaded by

dearysg2002
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online on Scribd
4K views

Algorithm Design Solutions

This document proves that the length of the shortest string that can be constructed as a concatenation of strings from two sets A and B, each containing at most n strings of maximum length L, is at most n^2L^2. It argues that if a string u of length greater than n^2L^2 could be constructed, the pigeonhole principle would imply two positions p and p' in u have the same type, and the substring between p and p' could be removed, contradicting u's minimality.

Uploaded by

dearysg2002
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 207

Suppose m ≤ n, and let L denote the maximum length of any string in A ∪ B.

Suppose
there is a string that is a concatenation over both A and B, and let u be one of minimum
length. We claim that the length of u is at most n2 L2 .
For suppose not. First, we say that position p in u is of type (ai , k) if in the concatenation
over A, it is represented by position k of string ai . We define type (bi , k) analogously. Now,
if the length of u is greater than n2 L2 , then by the pigeonhole principle, there exist positions
p and p in u, p < p , so that both are of type (ai , k) and (bj , k) for some indices i, j, k. But
in this case, the string u obtained by deleting positions p, p + 1, . . . , p − 1 would also be a
concatenation over both A and B. As u is shorter than u, this is a contradiction.

1
ex690.144.299

You might also like