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.
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).
Thanks a lot.
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 .
Not really 'same', but this one seems simillar.
http://main.edu.pl/en/archive/oi/7/pow
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!
Here's an interesting problem: given a string output it's K-th lexicographically unique substring.
SIS A' offset problem huh? :)
:)
Interesting problem. Can you provide any link to that problem?
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.
just received easy AC with suffix array, time = 0.03
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 :)
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.
thanks a lot! :) i have the idea using the O(N) iteration every query... now i got the perfect idea.. thanks! :)
Is there any mistake in this (after finding lcp array)?
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?
It's easy to solve using Suffix Automata
http://www.codeforces.com/problemset/problem/129/Ddo you mean this problem?
Can someone please provide links to other problems ? I mean of problems 5,8 and 9.
These are the ones I could find:
5 -> seti (in Romanian)
8 -> template
9 -> repeats (no test data)
10 -> period
thanx a lot :)
ivplay, if you ever happen to meet me, do ask for a treat. I owe you big time for this resource.