这道题目作为压轴倒没有前面两题难了,简单分为两部分实现操作:
1.统计子串在A中出现次数
2.二分查找确定输出的答案长度
第一步方法挺多的,比如说KMP或者用字符串哈希表优化后暴力，而该AC代码就是借助了一下KMP的方法实现，每次查找到子串后后移一位继续找。这一段时间复杂度为O(len_A).
我们选择利用substr()截取最长前缀,由于是前缀字符串，所以肯定从下标0开始，一直到最长前缀的最后一个下标，这里可以把截取终点的位置看作最长前缀的长度,所以我们求最长前缀长度即可。
这里，我们使用二分查找来确定最长前缀的长度,而该方法也是实现本步骤的最优解。我们每次取中间长度的前缀,然后查找其在字符串A中出现的次数。如果出现次数≥n,我们就尝试更长的前缀，否则尝试更短的。这里就不展开讲了,套套模板就行。由于查找范围为1~len_B，所以二分查找次数为O(len_B).
对于每个前缀字符串，都需要查找其长度,每次都需要O(len_A) 的时间,因此,代码的总时间复杂度为:
可以很好的处理给定范围内的数据。
既然讲了这么久了,那我们就直接来看满分的AC代码：
所以为什么T4和T6都是二分呢(T4看成01背包导致被硬控,虽然后面意识到补兑换二分做出来了)
唉我去,才发现我第一次写这么长的题解......
