给定2个字符串s1和s2和正整数k,其中s1长度为n1,s2长度为n2,在s2中选一个子串

要求选出的子串在s1中至少出现k次，求这样的子串的个数。

首先可以使用暴力枚举的方法来解决这个问题，即枚举s2中所有的子串，在s1中计算其出现次数，时间复杂度为O(n1*n2^2)，不过显然这种算法会超时。

因此，需要寻找更优秀的解决方法。可以考虑使用字符串哈希的方法，将s1和s2分别哈希，然后对于s2中的每个子串，计算其哈希值，然后在s1中使用哈希值进行查找，可以将时间复杂度降至O(n1+n2^2)。

具体实现时，需要注意哈希冲突的问题，可以使用双重哈希的方法，即使用两个不同的哈希函数计算哈希值。同时还需要注意随机化哈希函数的选择，以防止出现特定的字符串使得哈希函数效果变差。

虽然使用字符串哈希的方法可以降低时间复杂度，但仍需要对每个子串进行哈希计算和查找，对于较大的字符串而言，仍然会有较大的时间开销。因此，还可以考虑使用滑动窗口的方法，即每次移动s2中选取的子串时，只需要计算新增字符和删除字符对应的哈希值的差值，避免了重复计算，可以将时间复杂度降至O(n1+n2)。

综上所述，可以使用字符串哈希和滑动窗口的方法实现对问题的高效求解。