Given a string S
consisting of N
lowercase English alphabets.
Suppose we have a list L
consisting of all non empty substrings of the string S
.
I need to count the number of ways to choose exactly K
equal strings from the list L
(note that length of substring is not necessary to be equal to k
).
1 ≤ N ≤ 5000
1 ≤ K ≤ 10^9
Exampple:
Let S=ababa.
As List L = {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba", "abab", "baba", "ababa"}
let k=2
The number of ways will be 7:
("a", "a")
("a", "a")
("a", "a")
("b", "b")
("ab", "ab")
("ba", "ba")
("aba", "aba")
Similarly:
let k=3
The no of ways will be 1:
("a", "a", "a")
Build suffix array for given string.
Walk for this array, look for common starting symbols of (at least k) neighbour siffixes.