I wish everyone is doing well and happy .
Lately I learned Suffix Array and I'm trying to solve this problem (UVA — 760 DNA Sequencing), the problem is a merely application on finding the LCS (Longest Common Substring) of two strings .
- The problem in a nutshell : given two strings A,B (|A|,|B| <= 300) print all LCS of these two strings in lexicographical order .
- What I did : concatenate the two strings in a third string C and build the suffix array and the LCP (Longest Common Prefix) for C then iterate over the LCP table and find the longest LCP among all LCPs, say
maxLCP then iterate over the LCP table again, now once an LCP matches
maxLCP check whether the two suffixes belong to a different strings (A,B) if they do, print this LCP, if there is no LCP found print "No Common Sequence" as the problem states .
Here is my code .
Code after removing the duplicated LCS .
Shouldn't my approach work ?
I've tried many testcases and my code does produce the correct output for them, I got stuck on this problem for more than two days, read the code and revise the algorithm so many times, and couldn't figure out where's my fault .
Any help would be highly appreciated,
Thanks in advance and thank you for taking time to read my blog and good luck in the upcoming round tomorrow :D .
UPD : Thanks community, got AC after 15 submissions :D, as Urbanowicz indicated, I should print just unique LCSs