ACGO #挑战赛15th T6压轴题解

这道题目作为压轴倒没有前面两题难了,简单分为两部分实现操作:
1.统计子串在A中出现次数
2.二分查找确定输出的答案长度

第一步方法挺多的,比如说KMP或者用字符串哈希表优化后暴力，而该AC代码就是借助了一下KMP的方法实现，每次查找到子串后后移一位继续找。这一段时间复杂度为O(len_A).

我们选择利用substr()截取最长前缀,由于是前缀字符串，所以肯定从下标0开始，一直到最长前缀的最后一个下标，这里可以把截取终点的位置看作最长前缀的长度,所以我们求最长前缀长度即可。

这里，我们使用二分查找来确定最长前缀的长度,而该方法也是实现本步骤的最优解。我们每次取中间长度的前缀,然后查找其在字符串A中出现的次数。如果出现次数≥n,我们就尝试更长的前缀，否则尝试更短的。这里就不展开讲了,套套模板就行。由于查找范围为1~len_B，所以二分查找次数为O(len_B).

对于每个前缀字符串，都需要查找其长度,每次都需要O(len_A) 的时间,因此,代码的总时间复杂度为:

可以很好的处理给定范围内的数据。

既然讲了这么久了,那我们就直接来看满分的AC代码：

#include <bits/stdc++.h>

using namespace std;

//统计字符串A中子串出现次数
int countOccurrences(const string &A, const string &pattern)
{
    int count = 0;
    int pos = 0;
    while ((pos = A.find(pattern, pos)) != string::npos) 
    {
        count++;
        pos++; 
    }
    return count;
}

string A,B;
int n;
int main() 
{
    cin >> A >> B >> n;
    int maxLen = 0; 
    int low = 1, high = B.size();
    //立即启动二分查找！
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        string prefix = B.substr(0, mid); 
        int occurrences = countOccurrences(A, prefix); 

        if (occurrences >= n)
        {
            maxLen = mid; 
            low = mid + 1; 
        } 
        else
            high = mid - 1; 
 }

    if (maxLen == 0) 
        cout << "IMPOSSIBLE" << endl;
    else 
        cout << B.substr(0, maxLen) << endl; 
    return 0;
}

所以为什么T4和T6都是二分呢(T4看成01背包导致被硬控,虽然后面意识到补兑换二分做出来了)
唉我去,才发现我第一次写这么长的题解......