区块链技术博客
www.b2bchain.cn

SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)的讲解

这篇文章主要介绍了SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)的讲解,通过具体代码讲解7420并且分析了SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7420.html。具体如下:

SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)

思路:广义

SAMSAM

构建文本串,然后用以一个

sz[p]sz[p]

表示状态

pp

包含多少个原串,以及用一个

pre[p]pre[p]

来去重,然后将每个串在

SAMSAM

上跑一遍,失配了说明不存在,否则输出

sz[u]sz[u]

时间复杂度:

O(nn)O(nsqrt{n})

貌似

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define IOS ios::sync_with_stdio(false),cin.tie(0) int n,q,pre[N]; string s[N]; struct SAM{ 	int last,cnt;int ch[N<<1][26],fa[N<<1],len[N<<1],sz[N]; 	void insert(int c){ 		int p=last,np=++cnt;last=np;len[np]=len[p]+1; 		for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np; 		if(!p) fa[np]=1; 		else { 			int q=ch[p][c]; 			if(len[q]==len[p]+1) fa[np]=q; 			else  { 				int nq=++cnt;len[nq]=len[p]+1; 				memcpy(ch[nq],ch[q],sizeof ch[q]); 				fa[nq]=fa[q],fa[q]=fa[np]=nq; 				for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq; 			} 		} 	} 	void build(){ 		cin>>n>>q;last=cnt=1; 		for(int i=1;i<=n;i++){	//广义SAM.  			cin>>s[i];last=1; 			for(int j=0;j<s[i].size();j++) insert(s[i][j]-'a'); 		} 		for(int i=1;i<=n;i++){ 			int u=1; 			for(int j=0;j<s[i].size();j++){	//在文本串上跑一遍SAM.  				int x=s[i][j]-'a'; 				u=ch[u][x]; 				for(int p=u;p&&pre[p]!=i;p=fa[p])  				pre[p]=i,sz[p]++;	//记录状态p的对应的模式串编号pre[p]  			}					//和状态p被多少个原串包含.  		} 	} 	void solve(){ 		while(q--){ 			string a; 			cin>>a; 			int ok=1,u=1; 			for(int i=0;i<a.size();i++){	//在文本串上跑一遍.  				int x=a[i]-'a'; 				if(!ch[u][x]){	//如果失配了说明不存在.  					ok=0; 					break; 				} 				u=ch[u][x]; 			} 			if(!ok) cout<<0<<endl; 			else cout<<sz[u]<<endl; 		}  	} }sam; int main(){ 	IOS; 	sam.build(); 	sam.solve(); 	return 0; } 

本文地址https://www.b2bchain.cn/7420.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们