CF113B Petr# 题解

· · 题解

洛谷传送门 | CF 传送门 1 | CF 传送门 2

众所周知，一篇文章需要一张头图：

注：这是主播使用单哈希被卡的真实场景，这件事告诉了我们一定不要使用单哈。

一道很水的 *2000 题。

题意：给你三个字符串 s,s_1,s_2，让你求一个字符串 T 满足为 s 的子串且开头为 s_1，末尾为 s_2。

一个浅显的暴力如下：暴力枚举字串 T 的开头与结尾，并判断其开头是否为 s_1，末尾是否为 s_2。

注意到此题 S 长度为 2000，O(n^3) 过不了，所以我们使用哈希进行 O(1) 比较，将时间复杂度削为 O(n^2)。

如何判断是否相等？考虑使用 set 去重，时间复杂度为 O(\log n)，n 为 set 中元素个数，但最劣情况为每次比较都入红黑树，所以变为 O(\log (l^2)) 化简为 O(2\log l)，其中 l 为 s 长度。那么时间复杂度来到了 O(l^2 \log l)，常数有 4\sim 6 倍（set 有 2 \sim 3 倍），再加上因 CF 评测机原因，会将时间乘 2，并不好过。

选择常数更小的 vector，每次插入均摊 O(1)，最后排序后使用 unique 去重。在排序时会有大概 1.39 的常数，时间较为充裕。

需要注意的是：考虑到 s_1 可能比 s_2 长，所以需要判断末尾要将所有的字符放下。

代码：

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define lowbit(x) (x)&(-x)
using namespace std;

typedef double db;
typedef long long ll;
typedef __int128 III;
const db eps=1e-6;
const int inf=1e9;
void ll_cmax(ll &a,ll b){a=a>b?a:b;}
void ll_cmin(ll &a,ll b){a=a<b?a:b;}
void int_cmax(int &a,int b){a=a>b?a:b;}
void int_cmin(int &a,int b){a=a<b?a:b;}
bool db_eq(db a,db b){return fabs(a-b)<eps;}
bool number(char ch){return ch>='0' && ch<='9';}
bool lower(char ch){return ch>='a' && ch<='z';}
int sqlong(int n){int sq=sqrt(n)+1;return min(sq,n);}

const int MAXN=1000000+5,B=10000103,M=1000000711;
string sb,se,s;
int x[MAXN],p[MAXN];

void Hash(string s)
{
    p[0]=1;
    for(int i=0;i<s.size();i++) x[i+1]=(x[i]*B+s[i]%M)%M,p[i+1]=p[i]*B%M;
}

ll query(int l,int r)
{
    r++;
    return (x[r]-x[l]*p[r-l]%M+M)%M;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>sb>>se;
    int len=s.size(),lenb=sb.size(),lene=se.size();
    Hash(sb);
    int k1=x[lenb];
    Hash(se);
    int k2=x[lene];
    Hash(s);
    ll ans=0;
    vector<int>s;
    for(int i=0;i<=len-lenb;i++)
    {
        if(query(i,i+lenb-1)!=k1) continue;
        for(int j=i;j<=len-lene;j++)
        {
            if(query(j,j+lene-1)!=k2 || j+lene-1<i+lenb-1) continue;
            s.push_back(query(i,j+lene-1));
        }
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    cout<<s.size()<<endl;
    return 0;
}
//by Matrix_Power

然后你就 WA on Test 41 。。。

？换个常数试试，WA on Test 42，再来！WA on Test 44，WA on Test 47。（照应前文）

所以我们要使用自然溢出！

考虑到 unsigned long long 自动将值模 2^{64} 所以我们可以利用这个特性，将数值改为 unsigned long long 类型，不需取模，然后就可以过了。

#include<bits/stdc++.h>
#define endl '\n'
//#define int unsigned long long
#define lowbit(x) (x)&(-x)
using namespace std;

typedef double db;
typedef long long ll;
typedef long long ll;
typedef __int128 III;
const db eps=1e-6;
const int inf=1e9;
void ll_cmax(ll &a,ll b){a=a>b?a:b;}
void ll_cmin(ll &a,ll b){a=a<b?a:b;}
void int_cmax(int &a,int b){a=a>b?a:b;}
void int_cmin(int &a,int b){a=a<b?a:b;}
bool db_eq(db a,db b){return fabs(a-b)<eps;}
bool number(char ch){return ch>='0' && ch<='9';}
bool lower(char ch){return ch>='a' && ch<='z';}
int sqlong(int n){int sq=sqrt(n)+1;return min(sq,n);}

const int MAXN=1000000+5;
string sb,se,s;
ull x[MAXN],p[MAXN],B=54083,M=169566629;

void Hash(string s)
{
    p[0]=1;
    for(int i=0;i<s.size();i++) x[i+1]=x[i]*B+s[i],p[i+1]=p[i]*B;
}

ull query(int l,int r)
{
    r++;
    return x[r]-x[l]*p[r-l];
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>sb>>se;
    int len=s.size(),lenb=sb.size(),lene=se.size();
    Hash(sb);
    ull k1=x[lenb];
    Hash(se);
    ull k2=x[lene];
    Hash(s);
    vector<int>s;
    for(int i=0;i<=len-lenb;i++)
    {
        if(query(i,i+lenb-1)!=k1) continue;
        for(int j=i;j<=len-lene;j++)
        {
            if(query(j,j+lene-1)!=k2 || j+lene-1<i+lenb-1) continue;
            s.push_back(query(i,j+lene-1));
        }
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    cout<<s.size()<<endl;
    return 0;
}
//by Matrix_Power

AC 记录