c/c++语言开发共享SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)

SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)

思路：广义$SAM$SAM构建文本串，然后用以一个$sz[p]$sz[p]表示状态$p$p包含多少个原串，以及用一个$pre[p]$pre[p]来去重，然后将每个串在$SAM$SAM上跑一遍，失配了说明不存在，否则输出$sz[u]$sz[u]。

时间复杂度：$O(nsqrt{n})$O(nn​)貌似

#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; } 

c/c++开发分享SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)地址：https://blog.csdn.net/weixin_45750972/article/details/107501804