SP8093 JZPGYZ - Sevenk Love Oimaster(广义SAM)

SP8093 JZPGYZ - Sevenk Love Oimaster(广义SAM)

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

时间复杂度：$O(n\sqrt{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://blog.csdn.net/weixin_45750972/article/details/107501804