TANGLED - Editorial

[kuruma]

PROBLEM LINKS

Practice

Contest

DIFFICULTY

Hard

PRE-REQUISITES

Suffix Arrays

Problem:

As stated on the problem statement:

For a string S=c₁ c₂ … c_N, let S[a,b] denote c_a c_a+1 … c_b-1 c_b, that is, the substring starting at a^th character and ending at b^th 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

Further helpful links to consult:

Suffix Array

LCP Array

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

[msehgal]

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

[aayush_code]

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.

[mugurelionut]

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).

[ayushrocker92]

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

[kuruma]

Done @mugurelionut Thanks

[mmaxio]

Problem links are example.com

[kuruma]

fixed Thanks

[ash1794]

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

[yleewei]

When will the completed editorial be published?

[kingarthurie]

This editorial will never be finished I guess…

[japoorv]

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