題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串 $s$，需要回答 $q$ 次詢問，每次詢問給出一對 $(x,y)$ ，意思是用 $s$ 的前綴 $s[1:x]$ 和后綴 $s[n?y+1:n]$ 拼起來后得到一個新的字符串 $t$，問 $t$ 在 $s$ 中的出現(xiàn)次數(shù)

題目分析：考慮對于一對詢問 $(x,y)$ 得到的 $t$，存在 $s[l:r]=t$，設(shè)斷點為 $x^{\prime }=l+x?1,y^{\prime }=r?y+1$ 不難看出 $s[l:r]$ 可以拆成 $s[l:x^{\prime }]+s[y^{\prime }:r]$，滿足
$$s[l:x^{\prime }]=s[1:x]$$$$s[y^{\prime }:r]=s[n?y+1:n]$$

如果對于 $KMP$ 正著、倒著分別建出 $next$ 樹后，上述公式的意義是：

點 $x^{\prime }$ 一定位于點 $x$ 的子樹中

點 $y^{\prime }$ 一定位于點 $n?y+1$ 的子樹中

所以問題轉(zhuǎn)換為了，兩棵子樹中，有多少對 $(x^{\prime },y^{\prime })$ ，滿足 $x^{\prime }+1=y^{\prime }$。

類比與子樹求交問題，我們只需要在一棵樹上沿著 $dfs$ 序建立主席樹，維護(hù)的是第二棵樹上 $dfs$ 序就可以快速求解了。

代碼：

// Problem: Pty loves string // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-7084 // Memory Limit: 524 MB // Time Limit: 10000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; struct Node {int l,r,sum; }tree[N*20]; char s[N]; int nt[N],L1[N],R1[N],L2[N],R2[N],dfn1,dfn2,rk[N],root[N],cnt; vector<int>node1[N],node2[N]; void dfs1(int u,int fa) {L1[u]=++dfn1;rk[dfn1]=u;for(auto v:node1[u]) {if(v==fa) {continue;}dfs1(v,u);}R1[u]=dfn1; } void dfs2(int u,int fa) {L2[u]=++dfn2;for(auto v:node2[u]) {if(v==fa) {continue;}dfs2(v,u);}R2[u]=dfn2; } void update(int num,int &k,int l,int r) {tree[cnt++]=tree[k];k=cnt-1;tree[k].sum++;if(l==r) return;int mid=(l+r)>>1;if(num<=mid) update(num,tree[k].l,l,mid);else update(num,tree[k].r,mid+1,r); } int query(int i,int j,int l,int r,int L,int R) {//[L,R]:cur [l,r]:targetif(L>r||R<l) return 0;if(L>=l&&R<=r) return tree[j].sum-tree[i].sum;int mid=(L+R)>>1;return query(tree[i].l,tree[j].l,l,r,L,mid)+query(tree[i].r,tree[j].r,l,r,mid+1,R); } void get_next() {int n=strlen(s+1);nt[1]=0;for(int i=2,j=0;i<=n;i++) {while(j!=0&&s[j+1]!=s[i]) {j=nt[j];}if(s[j+1]==s[i]) {j++;}nt[i]=j;}for(int i=1;i<=n;i++) node1[nt[i]].push_back(i);nt[n]=n+1;for(int i=n-1,j=n+1;i>=1;i--) {while(j!=n+1&&s[j-1]!=s[i]) {j=nt[j];}if(s[j-1]==s[i]) {j--;}nt[i]=j;}for(int i=1;i<=n;i++) node2[nt[i]].push_back(i); } void init(int n) {for(int i=0;i<=n+5;i++) {node1[i].clear(),node2[i].clear();}root[0]=0;tree[0].l=tree[0].r=tree[0].sum=0;cnt=1;dfn1=dfn2=0; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {int n,m;scanf("%d%d%s",&n,&m,s+1);init(n);get_next();dfs1(0,-1),dfs2(n+1,-1);for(int i=1;i<=n+1;i++) {root[i]=root[i-1];update(L2[rk[i]+1],root[i],1,n+1);}while(m--) {int x,y;scanf("%d%d",&x,&y);y=n-y+1;printf("%d\n",query(root[L1[x]-1],root[R1[x]],L2[y],R2[y],1,n+1));}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021HDU多校10 - 7084 Pty loves string(KMPnext树+主席树+dfs序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。