题解归档 - cf113B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf113B
• 本地来源：problems/cf113B/idea.md
• 题目链接：https://codeforces.com/contest/113/problem/B
• 原始标题：cf113B Petr#

思路

cf113B Petr

题意

给定字符串 t 以及前缀标识 s_begin、后缀标识 s_end。统计 t 的连续子串中，内容互不相同且同时以 s_begin 开头、以 s_end 结尾的子串个数。s_begin 与 s_end 允许在子串内重叠（样例 aba / ab / ba）。

做法

1. 用朴素匹配（或 KMP）找出 t 中所有 s_begin 的起始下标集合 L。
2. 找出所有 s_end 在 t 中作为后缀结束的下标集合 R（若 s_end 在 r 处结束，则起点为 r - |s_end| + 1）。
3. 枚举 (l, r) ∈ L × R，若 r ≥ l + max(|s_begin|, |s_end|) - 1，则子串 t[l..r] 合法；用双哈希 set<pair<ll,ll>> 去重计数。

复杂度：O(|t| · (|s_begin| + |s_end|) + |L| · |R|)，|t| ≤ 2000 足够。

注意

• 仅有 l ≤ r 不够，必须保证子串长度能同时容纳前缀与后缀。
• 按内容去重，不是按出现位置去重。

验证

• 官方四组样例通过。
• WSL 对拍 500 组（Kali 远端不可达时的替代验证）。

代码

来源：problems/cf113B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:13:07
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2005;
const ll mod1=1000000007;
const ll mod2=1000000009;
const ll base=911382323;
string s,ss,sd;
ll n,i,j,k,l,r,cnt,ans;
ll h1[maxn],h2[maxn],pw1[maxn],pw2[maxn];
vector<ll>ls,rs;
set<pair<ll,ll>>cccc;
pair<ll,ll>geth(ll l,ll r){
    ll x1=(h1[r+1]-h1[l]*pw1[r-l+1]%mod1+mod1)%mod1;
    ll x2=(h2[r+1]-h2[l]*pw2[r-l+1]%mod2+mod2)%mod2;
    return {x1,x2};
}
int main(){
    cin>>s>>ss>>sd;
    n=(ll)s.size();
    pw1[0]=pw2[0]=1;
    for(i=1;i<=n;i++){
        pw1[i]=pw1[i-1]*base%mod1;
        pw2[i]=pw2[i-1]*base%mod2;
    }
    for(i=0;i<n;i++){
        h1[i+1]=(h1[i]*base+s[i])%mod1;
        h2[i+1]=(h2[i]*base+s[i])%mod2;
    }
    cnt=(ll)ss.size();
    for(i=0;i+cnt<=n;i++){
        if(s.substr(i,cnt)==ss) ls.push_back(i);
    }
    cnt=(ll)sd.size();
    for(r=cnt-1;r<n;r++){
        if(s.substr(r-cnt+1,cnt)==sd) rs.push_back(r);
    }
    cnt=(ll)ss.size();
    k=(ll)sd.size();
    for(i=0;i<(ll)ls.size();i++){
        l=ls[i];
        for(j=0;j<(ll)rs.size();j++){
            r=rs[j];
            if(r<l+max(cnt,k)-1) continue;
            cccc.insert(geth(l,r));
        }
    }
    cout<<cccc.size()<<endl;
    return 0;
}