题解-CmdOI2019 口头禅

题面

CmdOI2019 口头禅

给 \(n\) 个 \(01\) 串 \(s_i\)，\(m\) 个询问问 \(s_{l\sim r}\) 的最长公共子串长度。

数据范围：\(1\le n\le 20000\)，\(1\le m\le 10^5\)，\(\sum |s_i|\le 4\cdot 10^5\)。

蒟蒻语

蒟蒻看到这个题口胡了一个做法，然后轻松拿到了最优解，发现这是道大水题。

什么猫树或分治我没听说过，反正广义 SAM 上枚举子串乱搞 \(\Theta(n\sqrt n\log n)\) 跑得飞快。

蒟蒻解

首先把串建成广义 SAM 没有问题，为了方便我写了盗版的 /ch。

离线询问，把 \([l_i,r_i]\) 这个询问挂到 \(r_i\) 上。

顺序枚举 \(r\)，同时干这些坏事：

把 \(r_i=r\) 的询问按 \(l_i\) 排序，设有 \(qn\) 个询问。

对于 SAM 的节点 \(p\)，维护 \(li_p\) 和 \(ri_p\)，表示 \(s_{1\sim r}\) 中这个以这个节点为子串的最右连续区间。

维护方法是枚举 \(s_r\) 的所有子串（暴力跳每个前缀的 \(fa\)，时间复杂度 \(\Theta(n\sqrt n)\)），通过 \(r-1\) 递推。

然后对于每个该串子串节点 \(p\)，lower_bound 找到第一个 \(l_i\ge li_p\)，对询问 \([i,qn]\) 的答案都与该节点代表最长串长度取 \(\max\)。

这东西根据单调性差分一下即可，然后就做完了。

代码

#include <bits/stdc++.h>

using namespace std;

//Start

typedef long long ll;

typedef double db;

#define mp(a,b) make_pair((a),(b))

#define x first

#define y second

#define be(a) (a).begin()

#define en(a) (a).end()

#define sz(a) int((a).size())

#define pb(a) push_back(a)

#define R(i,a,b) for(int i=(a),I=(b);i<I;i++)

#define L(i,a,b) for(int i=(b)-1,I=(a)-1;i>I;i--)

const int iinf=0x3f3f3f3f;

const ll linf=0x3f3f3f3f3f3f3f3f;

//Data

const int N=2e4,lN=4e5,qN=1e5;

int n,qn,ans[qN];

string s[N];

vector<pair<int,int>> que[N];

//SuffixAutoMoton

const int tN=(lN<<1)+1,cN=2;

int tn,ch[tN][cN],fa[tN],len[tN];

int newsam(){

	fill(ch[tn],ch[tn]+cN,-1),fa[tn]=-1;

	return tn++;

}

int rt=newsam(),t;

void extend(int c){

	int p=t,np=t=newsam();

	len[np]=len[p]+1;

	for(;~p&&!~ch[p][c];p=fa[p]) ch[p][c]=np;

	if(!~p) fa[np]=rt;

	else {

		int q=ch[p][c];

		if(len[q]==len[p]+1) fa[np]=q;

		else {

			int nq=newsam();

			copy(ch[q],ch[q]+cN,ch[nq]);

			len[nq]=len[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq;

			for(;~p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;

		}

	}

}

int li[tN],ri[tN],vis[tN];

//Main

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	cin>>n>>qn;

	R(i,0,n){

		cin>>s[i],t=rt;

		for(char c:s[i]) extend(c-'0');

	}

	R(i,0,qn){

		int l,r; cin>>l>>r,--l,--r;

		que[r].pb(mp(l,i));

	}

	fill(vis,vis+tn,-1);

	fill(li,li+tn,-2),fill(ri,ri+tn,-2);

	R(i,0,n){

		sort(be(que[i]),en(que[i]));

		vector<int> mx(sz(que[i])+1);

		int p=rt,now=0;

		for(char c:s[i]){

			int q=p=ch[p][c-'0']; now++;

			for(;~q&&vis[q]<i;q=fa[q]){

				vis[q]=i;

				if(ri[q]==i-1) ri[q]=i;

				else li[q]=ri[q]=i;

				int id=lower_bound(be(que[i]),en(que[i]),

					mp(li[q],-1))-be(que[i]);

				mx[id]=max(mx[id],min(len[q],now));

			}

		}

		R(j,0,sz(que[i])) mx[j+1]=max(mx[j+1],mx[j]);

		R(j,0,sz(que[i])) ans[que[i][j].y]=mx[j];

	}

	R(i,0,qn) cout<<ans[i]<<"\n";

	return 0;

}

祝大家学习愉快！

巴特西

题解-CmdOI2019 口头禅

题面

蒟蒻语

蒟蒻解

代码

最新文章

热门文章