T6 题解

大家在日常编程中可能频繁使用哈希算法，这里为大家介绍一种KMP算法的解法。我们知道，KMP算法中有一个next数组，那么它究竟是什么含义呢？当匹配过程中出现失配时，模式串会回退到前面的某个位置，而next数组就决定了这个回退位置。具体来说，失配位置对应的最长公共真前后缀的长度，决定了模式串回退的位置。基于此，我们可以借助next指针来进行相关计算。
首先，对匹配串执行一遍KMP算法。然后，创建一个桶数组，用于记录模式串中每个最长前缀的出现次数。最后，结合next数组进行一次拓扑排序，完成相关统计工作。

  string a, b;
    cin >> a >> b;
    //计算a中每一个点匹配到b的哪个位置
    auto t = find_occurrences(a, b);
    //next函数
    auto z = prefix_function(b);
    // debug(z);
    int nn = b.size();
    vector<int> bn(nn + 1);
    for (auto i: t)bn[i]++;
    //拓扑
    for (int i = nn; i; i--) {
        // debug(z[i- 1], i);
        bn[z[i - 1]] += bn[i];
    }
    int k;
    cin >> k;
    for (int i = nn; i; i--) {
        if (bn[i] >= k) {
            cout << b.substr(0, i) <<endl;;
            return;
        }
    }
    cout << "IMPOSSIBLE" << endl;

时间复杂度O(n)