# PROBLEM LINKS

# DIFFICULTY

Hard

# PRE-REQUISITES

Suffix Arrays

# Problem:

As stated on the problem statement:

For a string **S=c _{1} c_{2} … c_{N}**, let

**S[a,b]**denote

**c**, that is, the substring starting at

_{a}c_{a+1}… c_{b-1}c_{b}**a**character and ending at

^{th}**b**character. For each

^{th}**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:

Tester

Further helpful links to consult:

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