Ciallo～(∠・ω< )⌒★
MutU
·
·
题解
巡厨不请自来～(∠・ω< )⌒★
以下 $n=|s|$，$m=|t|$，数组下标从 $0$ 开始。
要我们求把 $s$ 取一段前缀 $p$ 和一段后缀 $q$，满足 $|p|+|q|<|s|$。求将这两段拼起来后的串中 $t$ 的出现次数之和。
对于完整存在于一段前缀或后缀中的 $t$，我们可以简单求出数量。具体而言，若 $s_{i...i+m-1}=t$，对答案的贡献是 $(1+n-i-m)\times(n-i-m)\div2+i\times(i+1)\div2$。
那么剩下的就是 $t$ 横跨两段的情况。
枚举 $t$ 在 $p$ 中的长度 $len_p$，同时得到 $t$ 在 $q$ 中的长度 $len_q=m-len_p$。
令所有可以作为 $t$ 前 $len_p$ 位左端点的位置的集合为 $A$，可以作为 $t$ 后 $len_q$ 位右端点的位置的集合为 $B$。那么对于 $x\in A$ 和 $y\in B$，如果满足 $y-x\ge|t|$，则贡献一种方案。
此时问题转化为二维偏序，考虑用树状数组维护。
注意到随着 $len_p$ 增大，$A$ 和 $B$ 的变化总数为 $O(n)$ 级别。利用哈希值在每个位置上二分可以求出这个位置往左或往右最多与 $t$ 的前或后若干位相同。然后简单维护修改即可。
```cpp
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int N = 400100;
const ull base = 29;
string s,t;
int n,m,ans;
int maxa[N],maxb[N];
vector <int> vea[N],veb[N];
ull p[N],hs[N],ht[N];
int gets(int l,int r){
if(l==0) return hs[r];
return hs[r]-hs[l-1]*p[r-l+1];
}
int gett(int l,int r){
if(l==0) return ht[r];
return ht[r]-ht[l-1]*p[r-l+1];
}
struct BIT{
int tree[N];
int lowbit(int x){
return x & (-x);
}
inline void updata(int x,int d){
int u=x;
while(u<=n){
tree[u]+=d;
u+=lowbit(u);
}
return;
}
int query(int x){
int u=x,ans=0;
while(u>0){
ans+=tree[u];
u-=lowbit(u);
}
return ans;
}
};
BIT A,B;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>s>>t;
n=s.size(),m=t.size();
p[0]=1,hs[0]=s[0]-'a'+1,ht[0]=t[0]-'a'+1;
for(int i=1;i<=n+2;i++) p[i]=p[i-1]*base;
for(int i=1;i<n;i++) hs[i]=hs[i-1]*base+(s[i]-'a'+1);
for(int i=1;i<m;i++) ht[i]=ht[i-1]*base+(t[i]-'a'+1);
for(int i=0;i<=n-m;i++){
if(gets(i,i+m-1)==ht[m-1]) ans+=(1+n-i-m)*(n-i-m)/2+i*(i+1)/2;
}
for(int i=0;i<n;i++){
int l=1,r=max(m,n-i);
while(l<=r){
int mid=l+r>>1;
if(gets(i,i+mid-1)==gett(0,mid-1)) maxa[i]=mid,l=mid+1;
else r=mid-1;
}
l=1,r=max(m,i+1);
while(l<=r){
int mid=l+r>>1;
if(gets(i-mid+1,i)==gett(m-mid,m-1)) maxb[i]=mid,l=mid+1;
else r=mid-1;
}
vea[maxa[i]].push_back(i);
veb[maxb[i]].push_back(i);
}
for(int i=0;i<n;i++) A.updata(i+1,1);
for(int i=0;i<veb[m].size();i++) veb[m-1].push_back(veb[m][i]);
int cnt=0;
for(int i=1;i<m;i++){
int j=m-i;
for(int k=0;k<vea[i-1].size();k++){
int u=vea[i-1][k];
if(u+m<=n) cnt-=(B.query(n)-B.query(u+m));
A.updata(u+1,-1);
}
for(int k=0;k<veb[j].size();k++){
int u=veb[j][k];
cnt+=A.query(u-m+1);
B.updata(u+1,1);
}
ans+=cnt;
}
cout<<ans;
return 0;
}
```
###### 但是魔女的夜宴真的很好玩啊。