fail 树上二维数点 | QOJ5256. Insertions
Mirasycle
·
·
算法·理论
给定三个串 S,T,P，需要在 S 中插入 T（可以在开头或者末尾），求所有插入位置中与模式串 P 匹配次数最多的位置个数，最靠前的位置，最靠后的位置。字符串长度均 \le 10^5。
一道很巧妙的字符串匹配题，并不需要用什么高级后缀结构。
题目给的几个小问启发我们其实应该是转化为求出在每个位置插入的匹配次数，而非单纯找一些最大的。
记 S,T,P 的长度分别为 n,m,p。
有一些很显然的匹配形式，假设我们在 S(i,i+1) 处插入字符串 T，那么 S[1:i],S[i+1:n],T[1:m] 都是可以直接和 P 匹配的，这个可以用哈希来预处理前后缀匹配数。
还有一些比较难处理，我们分成两类，一种是 S[l:i]+T[1,r] 或 T[l,m]+S[i+1,r]，另一种是 S[l:i]+T+S[i+1,r]。
对于模式串 P 以及其反串建立 fail 树。
第一类匹配
对于第一种匹配两个类别是对称的，不妨讨论 S[l:i]+T[1,r]，也就是一段前缀拼后缀。
我们用 T 的前缀 T[1:j] 匹配 P 的后缀 P[p-j+1:p]（字符串哈希统计），对于符合要求的匹配点 p-j+1 我们在 fail 树上标记一下这个点的上一个位置 p-j (代表如果 S 能匹配到 p-j，就能和后面的连一起产生贡献) 。注意为了不和之前预处理的匹配产生重复贡献，这里要求 p-j\neq 0，否则就退化为和 T[1:m] 匹配了。
然后我们只需要在 S 上满足前缀要求即可，可以维护当前 S[1:i] 的后缀与 P 的前缀匹配的最长位置，所有满足 S[1:i] 的后缀与 P 的前缀匹配的位置都是上述的最长位置跳 fail 得来的，于是也就是当前点到根节点路径上标记点的个数。
于是我们预处理标记点，然后对于 fail 树从根开始到每个节点做一遍路径和即可。
对于 T[l:m]+S[i+1:r] 我们在 P 反串的 fail 树上实现上述功能即可。
第二类匹配
对于第二类匹配类似地，我们找到所有的 (l,r) 满足 T=P[l:r]，同时必须满足 l\neq 1,r\neq n，否则会会和前面的统计产生重复贡献，标记二元组 (l-1,r+1)。
这次匹配比上次要求严格，上次只是到根路径上标记点个数，这次需要在两颗树上的到根路径都出现同一标记点才行，也就是就变成了两颗树上数两个点到根节点公共点个数的 ds 题，注意此处的公共点表示可以构成被标记的二元组 (l,r)。
做法类似于 IOI2018 werewolf 是对于标记点对 (p,q) 改为 (dfn_p,dfn_q)，注意两个 dfn 不同，分别表示在两颗树上 dfs 序。我们用扫描线来扫描第一颗树的 dfs 序，线段树维护第二颗树的 dfs 序，每次进行区间修改，单点查询即可。
```cpp
#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10;
void chkmax(int &x,int y){ x=x>y?x:y; }
void chkmin(int &x,int y){ x=x<y?x:y; }
int pre[maxn],suf[maxn];
struct Hash{
ull h[maxn],p[maxn];
void init(char *s,int n){
p[0]=1; for(int i=1;i<=n;i++) p[i]=p[i-1]*131;
for(int i=1;i<=n;i++) h[i]=h[i-1]*131+(s[i]-'a'+1);
}
ull get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; }
}h1,h2,h3;
struct BIT{
int c[maxn],n;
void init(int m){ n=m; memset(c,0,sizeof(c)); }
int lowbit(int x){ return x&-x; }
void add(int x,int v){ for(;x<=n;x+=lowbit(x)) c[x]+=v; }
int query(int x){ int res=0; for(;x;x-=lowbit(x)) res+=c[x]; return res; }
}g;
struct FailTree{
int f[maxn],dfn[maxn],cnt; vector<int> G[maxn];
int val[maxn],sz[maxn]; char s[maxn];
void kmp(int n){
f[0]=f[1]=0;
for(int i=2,j=0;i<=n;i++){
while(j&&s[i]!=s[j+1]) j=f[j];
if(s[i]==s[j+1]) j++;
f[i]=j;
}
}
int dfs(int u){
dfn[u]=++cnt; sz[u]=1;
for(auto v:G[u]){
val[v]+=val[u];
sz[u]+=dfs(v);
}
return sz[u];
}
void init(char *S,int n){
for(int i=1;i<=n;i++) s[i]=S[i]; kmp(n);
for(int i=1;i<=n;i++) G[f[i]].pb(i);
cnt=0; dfs(0);
}
int Next(int p,char c){
while(p&&s[p+1]!=c) p=f[p];
if(s[p+1]==c) p++; return p;
}
int get(int x){ return dfn[x]+sz[x]-1; }
}t1,t2;
char s[maxn],t[maxn],P[maxn]; int n,m,p,C=0,cur=0;
int pos[maxn],ans[maxn],A=0,A1=maxn,A2=-1,A3=0;
vector<pair<int,int> > upd[maxn],que[maxn];
int rev(int x){ return p-x+1; }
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>(s+1)>>(t+1)>>(P+1); n=strlen(s+1),m=strlen(t+1),p=strlen(P+1);
h1.init(t,m); h2.init(P,p); h3.init(s,n); g.init(p+1);
for(int i=1;i<=min(m,p-1);i++){
if(h1.get(1,i)==h2.get(p-i+1,p)) t1.val[p-i]++;
if(h2.get(1,i)==h1.get(m-i+1,m)) t2.val[p-i]++;
}
for(int i=p;i<=m;i++)
if(h1.get(i-p+1,i)==h2.get(1,p)) C++;
t1.init(P,p); reverse(P+1,P+1+p); t2.init(P,p);
for(int i=p;i<=n;i++)
if(h2.get(1,p)==h3.get(i-p+1,i)) pre[i]++;
for(int i=n-p+1;i>=1;i--)
if(h2.get(1,p)==h3.get(i,i+p-1)) suf[i]++;
for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
for(int i=n-1;i>=0;i--) suf[i]+=suf[i+1];
for(int i=0;i<=n;i++) ans[i]=pre[i]+suf[i+1]+C;
for(int i=n;i>=1;i--) pos[i]=t2.Next(pos[i+1],s[i]);
for(int i=0;i<=n;i++){
if(i) cur=t1.Next(cur,s[i]);
ans[i]+=t1.val[cur]+t2.val[pos[i+1]];
que[t1.dfn[cur]].pb(t2.dfn[pos[i+1]],i);
}
for(int i=2;i+m-1<=p-1;i++)
if(h1.get(1,m)==h2.get(i,i+m-1)) upd[t1.dfn[i-1]].pb(mp(rev(i+m),1)),upd[t1.get(i-1)+1].pb(mp(rev(i+m),-1));
for(int i=1;i<=p+1;i++){
for(auto z:upd[i]) g.add(t2.dfn[z.fi],z.se),g.add(t2.get(z.fi)+1,-z.se);
for(auto z:que[i]) ans[z.se]+=g.query(z.fi);
}
for(int i=0;i<=n;i++) chkmax(A,ans[i]);
for(int i=0;i<=n;i++)
if(ans[i]==A){ chkmin(A1,i); chkmax(A2,i); A3++; }
cout<<A<<" "<<A3<<" "<<A1<<" "<<A2<<endl;
return 0;
}
```