(RankList for this Question)
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