wa in SSTORY suffix arrays

general
,
1

i kept getting wa in suffix arrays could the author @kuruma or anyone provide good test cases

1 Like
2

I’m not sure if that problem can be solved with suffix arrays. The problem is that with suffix array/lcp approach you may miss the leftmost matching. Imagine lcp array k…(k + n)…k where the first k corresponds to the maximum common substring and all other lcp entries correspond to only one string. With simple approach you’ll treat the position in second string as suffix array index around the first k, however you should check all further lcp entries. Probably you can find minimum fast with segment tree, however I’m not sure if it passes the time limit. I’ve used suffix automaton for solving these.

2 Likes
3

@coda : Try this case

babaazzzzyy

badyybac

The suffix array will contain baa… (From 1st string ) , baba… ( from first string ) , bac ( from second string ) , bad from second string .

So if you are examining consecutive entries of SA then you will find a match at “baba” and “bac” and find the index of “ba” as 7 in second string , even though its actually at index 1 also .

Its likely that you may output “yy” instead of “ba” .

8 Likes
4

Sounds good … Can you please give me link or idea about suffix automaton?

5

@vineetpaliwal isn’t the answer to this test case “aba” and not “ba”?

6

What should be the answer ba or aba ?

7

you have to find the longest…

8

Should be ‘aba’

9

@all : Have edited to remove an “a” from second string . It was just unintentionally there .

10

@daiver19 : I have solved this problem using “Suffix Arrays” .

1 Like
11

okay got it

12

thax @vineeetpaliwal u were correct wish i could figure it out before :smiley:
thax a lot

i rectified the aecd acad case during the contest couldnt figure out this one

1 Like
13

@coda : Please upvote and accept . :slight_smile:

14

Sorry, but I don’t have any articles in english. You may try just to search for it. Also suffix trees should definitely solve this, however they’re harder to implement in my opinion.

15

I solved the problem with suffix array with the help of hashing. Though I didn’t figure out where my suffix array failed, I got ac using hash. My code with only suffix array also failed to the case from @vineetpaliwal.

16

sorry @vineetpaliwal i didnt know abt the “accept” thing and also the “award point” thing thax

17

i solved it with suffix arrays, only thing is you need to look more than just adjacent cells to find the required answer.

http://www.codechef.com/viewsolution/3606293 :smiley:

18

My code handles this case as well. But still, got WA.
Here’s the link to my code: http://ideone.com/wct7zH

19

My code handles the case posted by @vineetpaliwal. But still, got WA.

Here’s the link to my code: http://ideone.com/wct7zH

Can someone please help me find where I’m making the error?

20

generate some random test cases & then generate output from ac code & then check your code by yourself :slight_smile: