文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

（沒有做出來，這個ans的處理方式其實也不難想…qwq）

考慮把T都作為模板串加入trie樹
加入每個模板串自然就是按照i順序的
所以我們在插入t的時候沿途標記一下
新出現的未標記的i的間隔就是當前的i與上一次的標記的差-1
在其中一直取max即可得到最大間隔
不要忘記還有一個間隔是n-最后的標記值！

預處理完trie樹后就簡單了
讓s在trie樹上跑，跑到尾就返回尾的ans值即可
如果跑一半失配了說明沒有t符合條件，直接返回n即可

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long typedef unsigned long long ull; const int N = 6e6+100; const int M=1e6+10; const ll mod=199907210507; int n,m; int tr[N][4],tot=1,ans[N],id[N]; char s[N]; void build(int k){int l=strlen(s+1),p=1;for(int i=1;i<=l;i++){int a=s[i]-'a'+1;if(!tr[p][a]) tr[p][a]=++tot;p=tr[p][a];ans[p]=max(ans[p],k-id[p]-1);id[p]=k;} }int ask(){int l=strlen(s+1),p=1;for(int i=1;i<=l;i++){int a=s[i]-'a'+1;if(!tr[p][a]) return n;p=tr[p][a];}return ans[p]; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf(" %s",s+1);build(i);}for(int i=1;i<=tot;i++){ans[i]=max(ans[i],n-id[i]);}for(int i=1;i<=m;i++){scanf(" %s",s+1);printf("%d\n",ask());}return 0; } /* 9 6 10 5 6 2 10 10 7 3 2 9 1 4 4 3 2 16 4 10 3 5 2 7 1 9 3 8 2 10 */

總結

以上是生活随笔為你收集整理的YBTOJ：前缀询问（trie树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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