模板—字符串—后缀自动机（后缀自动机+线段树合并求right集合）

时间：2023-02-12 19:56:26

模板—字符串—后缀自动机（后缀自动机+线段树合并求right集合）

Code:

#include <bits/stdc++.h>

using namespace std;

#define N 100010

map <int,int> son[N<<1]; char str[N]; int root[N<<1],pla[N],len;

int tot=1,last=1,pre[N<<1],dis[N<<1],in[N<<1];

namespace Sam

{

	void insert(int x,int id)

	{

		int p=last,np=last=++tot; dis[np]=dis[p]+1,pla[id]=np;

		while(p&&!son[p][x]) son[p][x]=np,p=pre[p];

		if(!p) {pre[np]=1;return;} int q=son[p][x];

		if(dis[q]==dis[p]+1) {pre[np]=q;return;} int nq=++tot;

		dis[nq]=dis[p]+1,son[nq]=son[q],pre[nq]=pre[q],pre[q]=pre[np]=nq;

		while(p&&son[p][x]==q) son[p][x]=nq,p=pre[p];;

	}

}

using namespace Sam;

struct Node {int son[2],size;}node[N<<7];

namespace Tree

{

	int cnt;

	void pushup(int p) {node[p].size=node[node[p].son[0]].size+node[node[p].son[1]].size;}

	void merge(int &x,int y)

	{

		if(!y) return; if(!x) {x=y;return;}

		node[++cnt]=node[x],x=cnt;

		merge(node[x].son[0],node[y].son[0]),merge(node[x].son[1],node[y].son[1]),pushup(x);

	}

	void change(int &p,int l,int r,int x)

	{

		if(!p) p=++cnt; if(l==r) {node[p].size++;return;}

		int mid=(l+r)>>1;

		if(x<=mid) change(node[p].son[0],l,mid,x);

		else change(node[p].son[1],mid+1,r,x); pushup(p);

	}

}

using namespace Tree;

int main()

{

	queue <int> q;

	scanf("%s",str+1),len=strlen(str+1);

	for(int i=1;i<=len;i++) insert(str[i]-'a',i);

	for(int i=1;i<=len;i++) change(root[pla[i]],1,len,i);

	for(int i=2;i<=tot;i++) in[pre[i]]++;

	for(int i=1;i<=tot;i++) if(!in[i]) q.push(i);

	while(!q.empty())

	{

		int p=q.front(); q.pop(),in[pre[p]]--;

		if(!in[pre[p]]) q.push(pre[p]);

		merge(root[pre[p]],root[p]);

	}

}

　　

相关文章