yashi's blog

A Problem About Suffix Array
By yashi, history, 9 years ago, In English

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

  • Vote: I like it
  • +25
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Could I ask what's wrong with my post ?
Why I got downvotes, I got stuck on this problem for long time, and tried so many ways to figure what's wrong in my code/algorithm and couldn't, eventually I posted this here looking for a help from the community, I tried to make the post clear, readable and obey the rules and the conventions of writing posts in the Codeforces .

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

What should be the answer for this input?

atgcatgc
atgc

I'd try to output only unique strings.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My code would produce atgc twice, the statement doesn't state anything related to the duplicated LCS but I think you're right, and it should be printed once
    I modified the code to print the resemble LCSs once, but still getting WA

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you very much, AC :D :D

    In addition of the unique LCS issue, the array of character isn't being erased when I overwrite it with the new string, I used memset and got AC

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yashi (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yashi (previous revision, new revision, compare).

→ Reply