3 ms·
The problem statement: "How does one detect when two strings overlap?" is inadequate. If "overlap" means "at least one substring in common", a trivial test for
by drallison 16y ago
The problem statement: "How does one detect when two strings overlap?" is inadequate. If "overlap" means "at least one substring in common", a trivial test for overlap would be to determine whether they have a character in common.
- drallison 16y agoI do not understand why this comment was down voted. When analyzing algorithms, a clear and correct statement of the problem is necessary and the one made here is clearly inadequate. For example, while the problem calls for an algorithm to "detect" overlap, while the algorithms described produce a list the overlapped strings. Moreover, there is no definition (other than the programs listed) for what is meant by "overlap". Consider "abc" and "abcd". The overlapping strings might be "a", "ab", "abc", "bc" , and "c" under one definition, or simply "abc" under another.
- endtime 16y ago>If "overlap" means "at least one substring in common" Why would it mean that? Is it not obvious that the common substring must be the beginning of one string and the end of the other?