题解归档 - cf427D

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

• 本地编号：cf427D
• 本地来源：problems/cf427D/idea.md
• 题目链接：https://codeforces.com/contest/427/problem/D
• 原始标题：CF427D Match & Catch

思路

CF427D Match & Catch

题意

给定两串小写字母 $s_1,s_2$（$|s_i|\le 5000$）。子串在串内唯一指：不存在另一段不同起点、长度相同且内容相同的子串。

求同时在两串中出现、且各自都唯一的最短公共子串长度；不存在输出 -1。

思路

答案具有单调性：若长度 $L$ 可行，则任意更长公共子串不必再考虑「更短」；因此从小到大枚举长度 $L=1,2,\ldots,\min(|s_1|,|s_2|)$，找到第一个可行 $L$ 即答案。

对每个固定 $L$：

1. 用双哈希统计 $s_1$ 中每个长度 $L$ 子串出现次数，保留次数为 $1$ 的哈希集合 $U$。
2. 统计 $s_2$ 中各子串出现次数。
3. 若存在哈希 $h$ 满足在 $s_1$、$s_2$ 中次数均为 $1$，则 $L$ 可行。

双哈希（模 $10^9+7$ 与 $10^9+9$，基数 $131$）降低碰撞风险；前缀哈希 $O(1)$ 取任意子串哈希。

复杂度

• 枚举长度：$O(n)$，$n\le 5000$。
• 每个长度扫两串：$O(n)$。
• 总时间 $O(n^2)$，空间 $O(n)$。

实现要点

• map<pair<ll,ll>,ll> 存哈希计数；仅当 cnt1==1 && cnt2==1 时返回当前 $L$。
• 暴力 brute.cpp 枚举 $s_1$ 子串 + compare 计数，用于 gen 小数据对拍。

样例

代码

来源：problems/cf427D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:42:45
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=5005,mod1=1000000007,mod2=1000000009,base=131;
string s1,s2;
ll h1a[maxn+5],h1b[maxn+5],h2a[maxn+5],h2b[maxn+5],pw1[maxn+5],pw2[maxn+5],n1,n2,i,j,k,zc,pd,cur,dq,cnt,ans;
map<pair<ll,ll>,ll>cccc,mp;
pair<ll,ll>geth(ll*h1,ll*h2,ll l,ll r){
    ll x1=(h1[r]-h1[l-1]*pw1[r-l+1]%mod1+mod1)%mod1;
    ll x2=(h2[r]-h2[l-1]*pw2[r-l+1]%mod2+mod2)%mod2;
    return {x1,x2};
}
void build(string&s,ll*h1,ll*h2){
    ll n=s.size();
    pw1[0]=pw2[0]=1,h1[0]=h2[0]=0;
    for(i=1;i<=n;i++){
        pw1[i]=pw1[i-1]*base%mod1;
        pw2[i]=pw2[i-1]*base%mod2;
        h1[i]=(h1[i-1]*base+s[i-1]-'a'+1)%mod1;
        h2[i]=(h2[i-1]*base+s[i-1]-'a'+1)%mod2;
    }
}
ll ok(ll L){
    cccc.clear(),mp.clear();
    pair<ll,ll>key;
    for(i=1;i+L-1<=n1;i++){
        key=geth(h1a,h1b,i,i+L-1);
        cccc[key]++;
    }
    for(i=1;i+L-1<=n2;i++){
        key=geth(h2a,h2b,i,i+L-1);
        mp[key]++;
    }
    for(autoit:cccc){
        if(it.second==1 and mp[it.first]==1) return 1;
    }
    return 0;
}
int main(){
    cin>>s1>>s2;
    n1=s1.size(),n2=s2.size();
    build(s1,h1a,h1b),build(s2,h2a,h2b);
    ans=-1;
    for(k=1;k<=min(n1,n2);k++){
        if(ok(k)){
            ans=k;
            break;
        }
    }
    cout<<ans<<"\n";
    return 0;
}