Problem # 26 : The Overlap sequence

Given an array of strings a$ containing strings a$(1) a$(2).....a$(n) it may be possible to reorder the strings a$(2) a$(3)...a$(n) such that each string in the reodered seqeunce can be split into two parts where the first part of a string is the same as the second part of the previous string in the sequence.

Note that a$(1) will always be the first string in the sequence and the maximum value of N=8.

For example if a$()=("start" isthmus artist hmusover ) the strings can be split as follows :-

start = st | art
artist = art | ist
isthmus = ist | hmus
hmusover= hmus | over

We write this reordered list as an overlap sequence. For the above the sequence should be printed as follows :-

start

  artist

     isthmus

        hmusover

Write a subroutine OVERLAP(a$() N) that outputs the overlap sequence of the strings in a$() provided such a sequence exists. This output is printed with the first character of the first word printed at (1 1) on the screen. A message No overlap sequence is printed on the top left of the screen if such a sequence does not exist. Assume that there can be atmost one overlap sequence for the given input and the first string in the sequence is a$(1) ie the first string in the array. Also note that both parts of the split string have to be non-empty.

Sample Output

N=6 a$(1)="begin" a$(2)="geremy" a$(3)="gerund" a$(4)="erger" a$(5)="under" a$(6)="ginger" OVERLAP(a$() n) should print this on a cleared screen :-

N=4 a$(1)="negate" a$(2)="tenet" a$(3)="netware" a$(4)="ware" OVERLAP(a$() n) should print No overlap sequence.

(Back to problems at The Vault )

LinkExchange Member