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

thanks a lot

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! :)

Iam getting TLE using suffix array on the 20th test case..construction algo used is n log^2 n

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(string_{i},string_{i - 1})) + 1). These strings are in lexigographic order, so I just subtractkuntil 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 :)

Problem 3

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/suffix-trees/practice-problems/algorithm/power-of-string-3/description/

I found here related to longest common substring and suffix array https://www.codechef.com/problems/SSTORY

I don't really get why is the solution for the second problem is to find the minimum rotation ? Thanks in advance ! :)

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