CF113B Petr# 题解

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

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

一道很水的 *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

长，所以需要判断末尾要将所有的字符放下。

代码：

CPP

#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 类型，不需取模，然后就可以过了。

CPP

#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 记录

文章操作

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

相关推荐

评论

CF113B Petr# 题解