A Problem About Suffix Array

Revision en3, by yashi, 2015-12-10 00:32:04

Hey Codeforces,
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

Tags suffix-array, strings, lcs


  Rev. Lang. By When Δ Comment
en3 English yashi 2015-12-10 00:32:04 144 Tiny change: ' /
en2 English yashi 2015-12-09 23:25:32 81
en1 English yashi 2015-12-09 02:34:24 1577 Initial revision (published)