4.2 Front to Back
(RankList for this Question)
Score: 60pts
Time Limit: 1.00 sec
You are given a string, find the number of common strings in the suffix and prefix array constructed from the given string

Constraints
\(1 \leq n \leq 9000\)
String contains only lowercase letters

Input Format
The first line contains the length of the string.
Second line contains the actual string of length \(n\).

Output Format
Print the number of common strings in the prefix and suffix array.

Example 1
Input:
5
abaab

Output:
2

Explanation:
For the string abaab the suffix and prefix arrays are:-
Prefix = [abaab, abaa, aba, ab, a]
Suffix = [abaab, baab, aab, ab, b]
Here the output is 2 since there are 2 common strings “abaab” and “ab”.

Example 2
Input:
5
rahul

Output:
1

Explanation:
For the string abaab the suffix and prefix arrays are:-
Prefix = [rahul, rahu, rah, ra, r]
Suffix = [rahul, ahul, hul, ul, l]
Here the output is 1 since there is only 1 string common in both the arrays”.

Log In to solve the Question