ivplay's blog

suffix array related problems
By ivplay, 10 years ago, In English

I have learned suffix array from this pdf:- Suffix arrays – a programming contest approach Adrian Vladu and Cosmin Negruşeri (appearedin GInfo 15/7, November2005)

Whatever there are some very good problems discussed in the pdf , and I want to practice them,test them with my code. Unfortunately I don't find those problems in any OJ or somewhere else to test them. Because some of the descriptions look like "training camp 2003" , i don't know which training camp or where to go. If somebody knows the source of the problems used in this article , please let me know. Sorry for such a large post.

If you are just learnt suffix array, try those problems discussed in this article. those are really awesome.

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

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

I found these:

1 -> Hidden Password

4 -> guess

6 -> Common subsequence

7 -> The longest palindrome

P.S: I'm not sure but I remember to saw problem 8 and 9, I can't remember if the problems were exactly or a little bit different but they can be found (I think).

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

    Thanks a lot.

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

    Problem 6: common subsequence (Polish Olympiad 2001 and Top Coder 2004) , requires to find longest common substring of three given strings . But this problem from spoj requires lcs from 2 strings . Dont know where to find the orginal problem and submit .

    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

If you use Codechef's problem tags to find problems involving suffix array technique,these (http://www.codechef.com/tags/problems/suffix-array) problems comes up. Some of them are very good and Codechef always has such detailed editorial. :)

Have fun!

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

Here's an interesting problem: given a string output it's K-th lexicographically unique substring.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    SIS A' offset problem huh? :)

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

    Interesting problem. Can you provide any link to that problem?

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

      Kth unique substring search related problem: http://www.spoj.com/problems/SUBLEX/

      But i don't know if we can solve this problem with suffix array. I think this can occur TLE.

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

        just received easy AC with suffix array, time = 0.03

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

          can u please share the idea? i solved that provlem usong Suffix automata. But i have an idea with Suffix array, don't think that will pass.... but i need to submit that code :D iff u can please share ur idea :)

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

            build suffix array (sa) and lcp array (lcp). For each suffix, number of distinct substrings equals to cnt[i] = n - sa[i] - lcp[i]. Then we can calculate the prefix sums for cnt array and answer the queries using binary search or two pointers.

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

              thanks a lot! :) i have the idea using the O(N) iteration every query... now i got the perfect idea.. thanks! :)

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it -6 Vote: I do not like it

              Is there any mistake in this (after finding lcp array)?

              int m=lower_bound(cnt,cnt+n,k)-cnt; //k = query
if(m)k-=cnt[m-1];
cout<<s.substr(sa[m],k)<<endl;
              → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am getting WA again and again, I am not even Binary Searching, complexity is O(N) per query. I built the suffix array and found LCP between every 2 consecutive strings. For first string number of distinct substrings are (len- (indexOf1stString) + 1). For others, number of distinct substrings are (len — (indexOfTheseStrings + LCP(stringi, stringi - 1)) + 1). These strings are in lexigographic order, so I just subtract k until I get 0. Is something wrong in this?

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

        It's easy to solve using Suffix Automata

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

    http://www.codeforces.com/problemset/problem/129/Ddo you mean this problem?

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

Can someone please provide links to other problems ? I mean of problems 5,8 and 9.

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

ivplay, if you ever happen to meet me, do ask for a treat. I owe you big time for this resource.

→ Reply