CSE2304, Prac' 3, week 6 and 7, 12 - 23 April 1999

Read all of this document before starting to write a program.

Write a program to read a string of characters from standard input, ignoring all characters that are not in a certain `alphabet'. The program must find and print the locations and length of the longest repeated substring in the string. (Resolve ties arbitrarily.)

The program must do this by sorting the substrings. The longest repeated substring can then be found by examining adjacent substrings; it must be a prefix of two (or more) adjacent substrings after sorting, e.g.:

mississippi
ississippi
ssissippi
sissippi
issippi
ssippi
sippi
ippi
ppi
pi
i

i
ippi
issippi     ***
ississippi  ***
mississippi
pi
ppi
sippi
sissippi
ssippi
ssissippi

The longest repeated substring, `issi', is of length 4 and starts at positions 2 and 5 in the original string (numbered from 1 up), and can be found from entries 3 and 4 (asterisked) in the sorted list.

• Your program must be efficient! Its average time and space complexity should be O(n log(n)), or very close to it, or better, for a string of length n. i.e. O(n²) is not good enough.
• Instrument the program so that it counts the number of character-to-character comparisons performed, prints the total and compares it to n, n log(n) and n².
• Note that a substring can be represented by its start position in the string. (Even to make copies of the characters of the substrings and to print them would take O(n²)-space and time.)

2. Use the program to find the longest repeated substring of the DNA sequence in the second half of the file HUMHBB.html, i.e. over the alphabet {a,c,g,t}, ignoring any other characters.

The demonstrator must see the program running on this and possibly on other strings of similar length (73K+).

Notes

• You will receive zero marks if you use a slow O(n²)-time sorting algorithm.
• You must not use a library sorting routine; you must write your own, otherwise you will receive zero marks.
• You may use the standard routines strcmp() or strncmp() for comparing (sub-)strings, or you can write your own.
• The suffix-tree is a data structure that can solve this problem in linear-time, but do not use it.
• An algorithm for this problem might be useful in file compression, plagiarism detection or molecular biology.

L.Allison, Comp. Sci. and S.W.E., Monash University, Australia.