Practice

Contest

Hard

Suffix Arrays

# Problem:

As stated on the problem statement:

For a string S=c1 c2 … cN, let S[a,b] denote ca ca+1 … cb-1 cb, that is, the substring starting at ath character and ending at bth character. For each 1 ≤ i ≤ L, chef wants the children to know how many tuples (a, b, c, d) exist for which S1[a, b] = S2[c, d] and length of S1[a,b] is i.

# Quick explanation:

We can use the concept of suffix arrays to solve the problem along with the use of a stack data structure to solve queries fast.

# Detailed explanation:

The most naive solution for this problem has complexity O(N^2) and it involves checking all possible substrings of a string on the other string.

This solution solves Subtasks 1 and 2 only…

For the remaining subtasks O(NlogN) solution needs to be devised using the concept of Suffix Arrays…

(Under construction…)

# Solutions:

Setter

Tester

Suffix Array

LCP Array

GInfo paper on “Suffix Arrays: A programming contest approach”

1 Like

cant we use KMP String Matcher. it is a linear time algo.

Is it possible to solve through DP ?

Example:

Input:

abab

babc

4

``````    b a b c
| | | |
a - 0 0 0 0 0

b - 0 0 1 0 0

a - 0 1 0 2 0

b - 0 0 2 0 0

0 1 0 3 0
``````

Now we can easily get the answer by traversing through the 2d array !

For L=1 We count all the elements greater than or equal to 1.

For L=2 We count all the elements greater than or equal to 2.

For L=3 We count all the elements greater than or equal to 3.

The “Stanford university paper” was only used as teaching material at Stanford, so it is incorrect to name it that. As you can see inside the paper, it was published in GInfo, a former Romanian Informatics magazine, which used to be quite popular in the Romanian Informatics community during the period 1998-2005. I would like to ask you to rename the link appropriately (e.g. “GInfo paper on …” would be OK, or anything containing the name of the GInfo magazine).

1 Like

exactly what m thinking!!!
generating all combinations n then kmp

1 Like

Done @mugurelionut Thanks

fixed Thanks

The setter’s solution is either incomplete or has some error. Can’t see the whole Code. Please look into it.

When will the completed editorial be published?

4 Likes

This editorial will never be finished I guess…

2 but won’t the patter processing for each character be O(n^2)

1 Like