给定由小写英文字母组成的字符串。
假设我们有一个列表S包含字符串N的所有非空子字符串。
我需要计算从列表中精确选择L相等字符串的方法数（注意，子字符串的长度不必等于S）。
1≤N≤5000
1≤K≤10^9
例如：
Let S=ababa.
As List L = {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba", "abab", "baba", "ababa"}
let k=2
方法数量为7：
("a", "a")
("a", "a")
("a", "a")
("b", "b")
("ab", "ab")
("ba", "ba")
("aba", "aba")
同样地：
let k=3
路数为1：
("a", "a", "a")
最佳答案
“所有子字符串的列表”。为什么你会有一个所有子串的列表假设你有一个一百万个字符的字符串，有5000亿个子字符串。解决这个问题根本不需要所有子串的列表。
如果K=0，则有一种方法。
如果K=1，则有N种方法。
对于k=1到n，长度k的每个子串可以从0到n-k的索引开始，即n-k+1个子串。识别不同的字符串并使用哈希表计算每个字符串的数目然后，对于发生n次的每个不同字符串，n>=k，将（n除以k）添加到您的计数中。
就这样。
首先查看长度为1的字符串，忽略长度小于K的所有字符串，计算方法数，然后为每个字符串添加另一个字符并重复，可以更快地完成此操作假设k=5，字符串中有一百万个字符，只有两个长度为6的子字符串出现了五次或更多次，那么只需要向这两个子字符串添加字符。
关于algorithm - 如何计算从列表L(所有子串的列表)中选择k个相等子串的方式的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30711272/