后綴自動機版本：

所有的串用(char)('z'+1)連起來，然后建自動機。再用原串在自動機上跑。跑到的位置的endpos就是出現的次數。不過內存有點大。

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <iomanip> #include <cstring> #include <map> #include <queue> #include <set> #include <cassert> #include <stack> #include <bitset> #define mkp make_pair using namespace std; const double EPS=1e-12; typedef long long lon; const lon SZ=2000010,SSZ=2*SZ,APB=27,one=1,INF=0x7FFFFFFF,mod=1000000007; int n,len,cnt,slink[SSZ],nex[SSZ][APB],maxlen[SSZ]; int minlen[SSZ],endpos[SSZ],in[SSZ]; char ch[SZ]; string str[SZ]; bool green[SSZ];void add(string &x) {for(int i=0;i<x.size();++i){ch[++len]=x[i];}ch[++len]='z'+1; }int ins(int pre,int c) {int z=++cnt,u=pre;green[z]=1;for(;u!=-1&&!nex[u][c];u=slink[u])nex[u][c]=z;maxlen[z]=maxlen[pre]+1;if(u==-1){slink[z]=0;}else{int x=nex[u][c];if(maxlen[x]==maxlen[u]+1){slink[z]=x;}else{int v=++cnt;memcpy(nex[v],nex[x],sizeof(nex[x]));maxlen[v]=maxlen[u]+1;slink[v]=slink[x];minlen[v]=maxlen[slink[v]]+1;slink[x]=slink[z]=v;minlen[x]=maxlen[v]+1;for(;u!=-1&&nex[u][c]==x;u=slink[u])nex[u][c]=v;}}minlen[z]=maxlen[slink[z]]+1;return z; }void topo() {for(int i=1;i<=cnt;++i){++in[slink[i]];}stack<int> stk;for(int i=1;i<=cnt;++i){if(!in[i])stk.push(i),endpos[i]=1;}for(;stk.size();){int top=stk.top();stk.pop();int pre=slink[top];endpos[pre]+=endpos[top],--in[pre];if(!in[pre]&&pre){if(green[pre])++endpos[pre];stk.push(pre);}} }void init() {cin>>n;for(int i=1;i<=n;++i){cin>>str[i];add(str[i]);}int pre=0;slink[0]=-1;for(int i=1;i<=len;++i){pre=ins(pre,ch[i]-'a');}topo(); }int calc(string &x) {int cur=0;for(int i=0;i<x.size();++i){int c=x[i]-'a';cur=nex[cur][c];}return endpos[cur]; }void work() {for(int i=1;i<=n;++i){cout<<calc(str[i])<<endl;} }int main() {std::ios::sync_with_stdio(0);//freopen("d:\\1.txt","r",stdin);int casenum;//cin>>casenum;//cout<<casenum<<endl;//for(int time=1;time<=casenum;++time)//for(int time=1;cin>>n>>qnum,n;++time) {//cout<<"Case "<<time<<": "; init();work();}return 0; }

?

轉載于:https://www.cnblogs.com/gaudar/p/10740760.html

總結

以上是生活随笔為你收集整理的p3966单词的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。