A Problem About Suffix Array

Правка en3, от 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

Теги suffix-array, strings, lcs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский yashi 2015-12-10 00:32:04 144 Tiny change: ' /
en2 Английский yashi 2015-12-09 23:25:32 81
en1 Английский yashi 2015-12-09 02:34:24 1577 Initial revision (published)