ivplay's blog

By ivplay, 5 years ago, ,

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.

• +4

 » 5 years ago, # |   +4 I found these:1 -> Hidden Password4 -> guessP.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).
•  » » 5 years ago, # ^ |   0 Thanks a lot.
•  » » 3 years ago, # ^ |   0 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 .
•  » » » 3 years ago, # ^ |   +3 Not really 'same', but this one seems simillar.http://main.edu.pl/en/archive/oi/7/pow
•  » » » » 3 years ago, # ^ |   0 thanks a lot
 » 5 years ago, # | ← Rev. 4 →   +9 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!
 » 5 years ago, # |   +4 Here's an interesting problem: given a string output it's K-th lexicographically unique substring.
•  » » 5 years ago, # ^ |   +1 SIS A' offset problem huh? :)
•  » » » 5 years ago, # ^ |   +1 :)
•  » » 5 years ago, # ^ |   0 Interesting problem. Can you provide any link to that problem?
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   0 just received easy AC with suffix array, time = 0.03
•  » » » » » 4 years ago, # ^ |   0 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 :)
•  » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » » 4 years ago, # ^ |   0 thanks a lot! :) i have the idea using the O(N) iteration every query... now i got the perfect idea.. thanks! :)
•  » » » » » » » 4 years ago, # ^ |   0 Iam getting TLE using suffix array on the 20th test case..construction algo used is n log^2 n
•  » » » » » » » 2 years ago, # ^ |   -6 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<
•  » » » » » 3 years ago, # ^ |   0 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?
•  » » » » 4 years ago, # ^ |   +3 It's easy to solve using Suffix Automata
•  » » 3 years ago, # ^ |   0 http://www.codeforces.com/problemset/problem/129/Ddo you mean this problem?
 » 4 years ago, # |   0 Can someone please provide links to other problems ? I mean of problems 5,8 and 9.
•  » » 4 years ago, # ^ |   +1 These are the ones I could find:5 -> seti (in Romanian) 8 -> template 9 -> repeats (no test data) 10 -> period
•  » » » 4 years ago, # ^ |   0 thanx a lot :)
•  » » » » 2 years ago, # ^ |   0
 » 2 years ago, # |   0 I found here related to longest common substring and suffix array https://www.codechef.com/problems/SSTORY
 » 22 months ago, # |   0 I don't really get why is the solution for the second problem is to find the minimum rotation ? Thanks in advance ! :)
 » 12 months ago, # |   0 ivplay, if you ever happen to meet me, do ask for a treat. I owe you big time for this resource.