C15-T6 字符串匹配与前缀

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> compute_fail(const string& pattern) {
    int m = pattern.size();
    vector<int> fail(m, 0);
    for (int i = 1; i < m; ++i) {
        int j = fail[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        fail[i] = j;
    }
    return fail;
}
int count_occurrences(const string& text, const string& pattern, int k, const vector<int>& fail) {
    if (k == 0) return 0;
    int cnt = 0;
    int j = 0;
    for (char c : text) {
        while(j>0 &&c!=pattern[j]){
            j =fail[j- 1];
        }
        if(c ==pattern[j]){
            j++;
        }
        if(j== k){
            cnt++;
            j=fail[j - 1];
        }
    }
    return cnt;
}
string solve(const string& A, const string& B, int n) {
    if (n == 0) {
        int k = min(A.size(), B.size());
        if (k >= 1) {
            return B.substr(0, k);
        } else {
            return "IMPOSSIBLE";
        }
    }
    int mx= min(A.size(), B.size());
    if (mx == 0) {
        return "IMPOSSIBLE";
    }
    vector<int> fail =compute_fail(B);
    int l =0,r=mx;
    int best_k = 0;
    while (l<=r){
        int mid=(l+r+1)/2;
        if (mid==0) {
            r= mid - 1;
            continue;
        }
        int cnt=count_occurrences(A,B,mid,fail);
        if (cnt >= n){
            best_k = mid;
            l= mid + 1;
        } else {
            r=mid - 1;
        }
    }
    if (best_k>=1) {
        return B.substr(0, best_k);
    } else {
        return "IMPOSSIBLE";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string A,B;
    int n;
    cin>>A>>B>>n;
    if(B.empty()){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    string res=solve(A,B,n);
    cout<<res<<endl;
    return 0;
}