CF79C Beaver 题解

Lin_Yi_Rui · 2026-04-25 17:31:19 · 题解

题意

寻找主串中不包含任何匹配串的最大区间长度。

分析

首先要找到所有等于匹配串的区间。

那么问题变为：
给定若干区间，求不完整包含它们中任意一个的最大区间。

实现

匹配字符串可以使用字符串哈希实现。

然后对区间排序，显然两相邻区间产生的最大贡献为：

另外，第一个区间不止可以和第二个区间产生贡献，
它也可以和开头产生贡献，即 [0,r_1-1] 也是合法的。

同理，在最后 [l_n+1,end] 也是合法的。

注意

区间需要去重，防止如图的情况。

但这样显然不正确，因为包含了 $3$ 号区间。

因此我们要删除像 2 号区间这样，内部包含有其他区间的区间。

即保证区间右端点严格递增。
可以使用单调栈实现。

Code

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;

const int N = 1e5+5;
//使用双值哈希 更安全
ll mod[2] = {1000000009,999999937},base[2] = {20100719,1145141};
ll Hash(string s) {
    ll h0 = 0,h1 = 0;
    for(char c:s) {
        h0 = (h0*base[0]+c)%mod[0];
        h1 = (h1*base[1]+c)%mod[1];
    }
    return h0*(1000000000)+h1;
}

//单调栈去重
vector<pair<int,int>> v;
int sta[N],top = 0;
void Unique() {
    for(int i = 0; i < v.size(); i ++) {
        while(top && v[sta[top-1]].second >= v[i].second) top --;
        sta[top++] = i;
    }
}
int main() {
    string s;
    int n;
    cin >> s >> n;
    int len = s.size();
    while(n --) {
        string t;
        cin >> t;
        ll hs = Hash(t);
        for(int i = 0; i < len-(int)t.size()+1; i ++) {
            if(Hash(s.substr(i,t.size())) == hs)
                v.push_back({i,i+(int)t.size()-1});
        }
    }

    if(v.size() == 0) {
        cout << len << " 0";
        return 0;
    }
    sort(v.begin(),v.end());
    Unique();
    int pos = 0,ans = v[sta[0]].second;
    for(int i = 0; i < top; i ++) {
        if((i+1<top ? v[sta[i+1]].second:len) - v[sta[i]].first-1 > ans) {
            ans = (i+1<top ? v[sta[i+1]].second:len) - v[sta[i]].first-1;
            pos = v[sta[i]].first+1;
        }
    }
    cout << ans << " " << pos;
}

时间复杂度 O(|s|\cdot \sum |b_i|)。

但 Hash(s.substr(i,t.size())) 多次取子串的操作，
会造成额外的内存开销，常数较大。

因此可以使用前缀哈希进行优化

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const int N = 1e5+5;

string s;
int n,len;
struct HASH {
    ll mod[2] = {1000000009,999999937},base[2] = {20100719,1145141},powb[2][N];
    pll h[N];

    pll Hash_str(string s) {
        ll h0 = 0,h1 = 0;
        for(char c:s) {
            h0 = (h0*base[0]+c)%mod[0];
            h1 = (h1*base[1]+c)%mod[1];
        }
        return make_pair(h0,h1);
    }

    void init() {
        powb[0][0] = powb[1][0] = 1;
        for(int i = 1; i <= len; i ++) {
            h[i].first = (h[i-1].first*base[0]+s[i])%mod[0];
            h[i].second = (h[i-1].second*base[1]+s[i])%mod[1];

            powb[0][i] = (i==0?1:powb[0][i-1]*base[0])%mod[0];
            powb[1][i] = (i==0?1:powb[1][i-1]*base[1])%mod[1];
        }

    }
    pll Hash_main(int l,int r) {
        return make_pair((h[r].first- h[l-1].first*powb[0][r-l+1]%mod[0] +mod[0])%mod[0],
                        (h[r].second- h[l-1].second*powb[1][r-l+1]%mod[1] +mod[1])%mod[1]);
    }
}Hash;

vector<pair<int,int>> v;
int sta[N],top = 0;
void Unique() {
    for(int i = 0; i < (int)v.size(); i ++) {
        while(top && v[sta[top-1]].second >= v[i].second) top --;
        sta[top++] = i;
    }
}

int main() {

    cin >> s >> n;
    len = s.size();
    //下标从 1 开始 方便计算
    s = " "+s;
    Hash.init();
    while(n --) {
        string t;
        cin >> t;
        pll hs = Hash.Hash_str(t);
        for(int i = 1; i <= len-(int)t.size()+1; i ++) {
            if(Hash.Hash_main(i,i+(int)t.size()-1) == hs)
                v.push_back({i,i+(int)t.size()-1});
        }
    }

    if(v.size() == 0) {
        cout << len << " 0";
        return 0;
    }
    sort(v.begin(),v.end());
    Unique();
    int pos = 1,ans = v[sta[0]].second-1;
    for(int i = 0; i < top; i ++) {
        if((i+1<top ? v[sta[i+1]].second:len+1) - v[sta[i]].first-1 > ans) {
            ans = (i+1<top ? v[sta[i+1]].second:len+1) - v[sta[i]].first-1;
            pos = v[sta[i]].first+1;
        }
    }
    cout << ans << " " << pos-1;
}

时间复杂度 O(n\cdot |s| + k\log k)

使用前缀哈希后，
预处理 O(|s|)，查询降到了 O(1)。