SP3109 STRLCP - Longest Common Prefix 题解

SP3109 STRLCP - Longest Common Prefix 题解

某省某年省选原题出处，看来 CCF 出原题这事由来已久。

简化题意

1. 让你维护一个字符串序列。
2. 支持单点修改。
3. 支持单点插入。
4. 支持询问两个子串的最长公共前缀。

解法

本篇题解前置芝士：无旋 Treap（FHQ Treap），哈希，二分。如果有不会的请自行查找资料学习。

如果没有单点插入操作，我们可以考虑使用线段树维护区间哈希值（我不会后缀自动机）。求最长公共前缀时可以二分最长公共前缀的长度，这里记作 $mid$，判断两个字符串前 $mid$ 个字符是否相同（即哈希值相等），如果相同则证明答案不小于 $mid$，将二分范围向右侧缩小，如果不相同则证明答案小于 $mid$，将二分范围向左缩小。

为什么这题不能用普通线段树呢？因为单点插入操作会改变序列长度，就会改变线段树中父亲与儿子的关系。

那有没有能同时支持动态维护序列和区间信息的数据结构呢？有，平衡树可以动态维护序列。相信大家都会平衡树的基本操作了，这里只有合并区间信息这里和模板题不一样。所以我只讲如何合并区间信息。

先看线段树是如何合并区间哈希值的。

注意到平衡树的性质，根节点表示的点在左右子树表示的区间的中间。所以类似于线段树的区间合并，平衡树的区间合并是三个区间的合并。

查询 $[l,r]$ 区间的哈希值时可以将平衡树分裂成 $[1,l-1],[l,r],[r+1,L]$ 三棵平衡树，查询后再将三棵平衡树合并即可。$L$ 表示当前序列的长度。

综上，平衡树的时间复杂度是 $\mathcal{O}((L+c)\log L+q{\log }^{2}L)$，分别是建树、修改、查询的时间复杂度，其中 $q$ 表示操作中查询次数，$c$ 表示操作中修改次数。

代码

#include<bits/stdc++.h>
namespace fast_IO
{
	/**
	 * 快读快写
	*/
};
using namespace fast_IO;
const int base=131;
int t,n,m,l,r,mid,ans;
char op,ch;
unsigned int pw[100010];
std::string st;
struct fhq_node
{
	int w,siz;
	unsigned int val,has;
	fhq_node *lc,*rc;
	inline fhq_node(unsigned int val)
	{
		this->val=has=val,w=rand(),siz=1,lc=rc=nullptr;
	}
	inline void pushup()
	{
		siz=(lc==nullptr?0:lc->siz)+(rc==nullptr?0:rc->siz)+1;
		if(lc==nullptr && rc==nullptr) has=val;
		else if(lc==nullptr) has=val*pw[rc->siz]+rc->has;
		else if(rc==nullptr) has=lc->has*pw[1]+val;
		else has=lc->has*pw[rc->siz+1]+val*pw[rc->siz]+rc->has;
	}
};
class fhq_treap
{
private:
	fhq_node *root;
	inline fhq_node *merge(fhq_node *l,fhq_node *r)
	{
		if(l==nullptr) return r;
		if(r==nullptr) return l;
		if(l->w<r->w)
		{
			l->rc=merge(l->rc,r),l->pushup();
			return l;
		}else
		{
			r->lc=merge(l,r->lc),r->pushup();
			return r;
		}
	}
	inline std::pair<fhq_node *,fhq_node *> split(fhq_node *rt,const int &k)
	{
		std::pair<fhq_node *,fhq_node *> ret;
		if(rt==nullptr) return std::make_pair(nullptr,nullptr);
		int left=rt->lc==nullptr?0:rt->lc->siz;
		if(k<=left) ret=split(rt->lc,k),rt->lc=ret.second,rt->pushup(),ret.second=rt;
		else ret=split(rt->rc,k-left-1),rt->rc=ret.first,rt->pushup(),ret.first=rt;
		return ret;
	}
	inline void clear(fhq_node *rt)
	{
		if(rt==nullptr) return;
		if(rt->lc!=nullptr) clear(rt->lc);
		if(rt->rc!=nullptr) clear(rt->rc);
		delete rt;
	}
public:
	inline int getsiz()
	{
		return root->siz;
	}
	inline void clear()
	{
		clear(root),root=nullptr;
	}
	inline void fix(const int &pos,const unsigned int val)
	{
		std::pair<fhq_node *,fhq_node *> a,b;
		a=split(root,pos),b=split(a.first,pos-1);
		b.second->val=b.second->has=val,root=merge(merge(b.first,b.second),a.second);
	}
	inline void insert(const int &pos,const unsigned int val)
	{
		fhq_node *rt=new fhq_node(val);
		std::pair<fhq_node *,fhq_node *> a;
		a=split(root,pos),root=merge(merge(a.first,rt),a.second);
	}
	inline unsigned int ask(const int &L,const int &R)
	{
		std::pair<fhq_node *,fhq_node *> a,b;
		a=split(root,R),b=split(a.first,L-1);
		unsigned int ret=b.second->has;
		root=merge(merge(b.first,b.second),a.second);
		return ret;
	}
};
fhq_treap tree;
int main()
{
	srand(time(0)),pw[0]=1;
	for(int i=1;i<=100001;i++) pw[i]=pw[i-1]*base;
	in>>t;
	while(t--)
	{
		in>>st>>m,st="#"+st,n=st.size()-1,tree.clear();
		for(int i=1;i<=n;i++) tree.insert(i,st[i]-'a'+1);
		for(int i=1,x,y;i<=m;i++)
		{
			in>>op>>x;
			if(op=='Q')
			{
				in>>y;
				if(x>y) std::swap(x,y);
				l=1,r=tree.getsiz()-y+1,ans=0;
				while(l<=r)
				{
					mid=(l+r)/2;
					if(tree.ask(x,x+mid-1)==tree.ask(y,y+mid-1)) ans=mid,l=mid+1;
					else r=mid-1;
				}
				out<<ans<<'\n';
			}else if(op=='R') in>>ch,tree.fix(x,ch-'a'+1);
			else in>>ch,tree.insert(x,ch-'a'+1);
		}
	}
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}