BZOJ 3796 Mushroom追妹纸

题目大意

给你三个字符串，求一个最长的字符串，使得这个字符串是A和B的子串同时C不是它的子串。

看到这样的字符串题直接二分加哈希啊～

这题有一个蛇皮的地方：关于标记的处理。我们需要处理的是一次修改，多次查询一个区间内有没有一个点被标记，解决方法是用前缀和优化，这样可以非常快速的解决。

时间复杂度$O(N \log N)$

#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int lena,lenb,lenc,flg[50020];
unsigned long long hsa[2][50020],hsb[2][50020],hsc[2],bs[2][50020];
char a[50020],b[50020],c[10010];
set<pair<unsigned long long,unsigned long long> >s;
void init()
{
	bs[0][1]=131,bs[1][1]=233;
	for(int i=2;i<=50000;++i) bs[0][i]=bs[0][i-1]*bs[0][1],bs[1][i]=bs[1][i-1]*bs[1][1];
	lena=strlen(a+1),lenb=strlen(b+1),lenc=strlen(c+1);
	for(int i=1;i<=lena;++i) hsa[0][i]=hsa[0][i-1]*bs[0][1]+a[i],hsa[1][i]=hsa[1][i-1]*bs[1][1]+a[i];
	for(int i=1;i<=lenb;++i) hsb[0][i]=hsb[0][i-1]*bs[0][1]+b[i],hsb[1][i]=hsb[1][i-1]*bs[1][1]+b[i];
	for(int i=1;i<=lenc;++i) hsc[0]=hsc[0]*bs[0][1]+c[i],hsc[1]=hsc[1]*bs[1][1]+c[i];
	for(int i=0;i+lenc<=lenb;++i) if(hsb[0][i+lenc]-hsb[0][i]*bs[0][lenc]==hsc[0]&&hsb[1][i+lenc]-hsb[1][i]*bs[1][lenc]==hsc[1]) flg[i+lenc]=1;
	for(int i=1;i<=lenb;++i) flg[i]+=flg[i-1];
	return;
}
bool check(int tx)
{
	s.clear();
	for(int i=0;i+tx<=lena;++i) s.insert(make_pair(hsa[0][i+tx]-hsa[0][i]*bs[0][tx],hsa[1][i+tx]-hsa[1][i]*bs[1][tx]));
	for(int i=0;i+tx<=lenb;++i)
		if((tx<lenc||flg[i+tx]==flg[i+lenc-1])&&s.count(make_pair(hsb[0][i+tx]-hsb[0][i]*bs[0][tx],hsb[1][i+tx]-hsb[1][i]*bs[1][tx]))) return true;
	return false;
}
int bisection()
{
	int l=1,r=min(lena,lenb)+1;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	return l-1;
}
int main()
{
	scanf("%s%s%s",a+1,b+1,c+1);
	init();
	printf("%d\n",bisection());
	return 0;
}