SP8093 JZPGYZ – Sevenk Love Oimaster(广义SAM)
思路:广义构建文本串,然后用以一个表示状态包含多少个原串,以及用一个来去重,然后将每个串在上跑一遍,失配了说明不存在,否则输出。
时间复杂度:貌似
#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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598550.html