ShinriiTin/templates/test
CF BETA #30 E.Tricky and Clever Password
检验模板：Kmp，Manacher，SparseTable
题目大意：
给出一个字符串\(S(|S|\le10^5)\)，要求将\(S\)分为若干个不相交的部分，满足\(S=A+prefix+B+middle+C+suffix\)。
要求\(|prefix|=|suffix|\)，\(|middle|\)为奇数，\(prefix+middle+suffix\)为回文串，除了\(middle\)之外任意一部分都可以为空。
现在要最大化\(|prefix|+|middle|+|suffix|\)，任意输出一种合法方案。
题解：
先枚举\(suffix\)然后找到最左边的可以与它匹配的\(prefix\)，可以用原串和反串做一次 Kmp 得到。
之后问题就转化为 \(n\) 次询问，每次询问某个区间中最大的回文串。
一种做法是二分答案，如果区间\([L+M-1,R-M+1]\)中最大的奇回文半径大于等于\(M\)，则存在长度为\(2M-1\)的奇回文串。
通过 ST 表预处理可以做到单次询问\(O(\log{n})\)。
总的时间复杂度为\(O(n\log{n})\)，空间复杂度为\(O(n\log{n})\)。
#include <bits/stdc++.h>
const int max_N=1e5;
//indexed from 1
template<size_t size>
struct Kmp{
int fail[size];
template<typename T>
inline void get_fail(T S,int len){
fail[1]=0;
for(int i=2,j;i<=len;++i){
for(j=fail[i-1];j&&S[j+1]!=S[i];j=fail[j]);
fail[i]= S[j+1]==S[i]?++j:0;
}
}
template<typename T>
inline void matching(T A,int lenA,T B,int lenB,int*right){
get_fail(B,lenB);
for(int i=1,j=0;i<=lenA;++i){
while(j&&A[i]!=B[j+1])j=fail[j];
if(A[i]==B[j+1])++j;
if(!right[j])right[j]=lenA-i+j;
if(j==lenB)return;
}
}
};
//indexed from 1
template<size_t size>
struct Manacher{
//type:ODD 1,EVEN 0
//define the center of even string as the left one
int r[2][size];
template<typename T>
inline void build(T S,int len,int type){
register int i,j,k;
int*R=r[type];
for(i=1,j=0;i<=len;i+=k,j=std::max(j-k,0)){
while(i-j>0&&i+j+type<=len&&S[i-j]==S[i+j+type])++j;
R[i]=j;
for(k=1;k<j&&R[i-k]!=R[i]-k;++k)R[i+k]=std::min(R[i-k],R[i]-k);
}
}
};
Manacher<max_N+21>manacher;
template<size_t size,size_t size_log>
struct SparseTable{
int max[size][size_log],bit[size];
inline int slt(int x,int y){
return manacher.r[0][x]>manacher.r[0][y]?x:y;
}
inline void init(int n){
for(int i=2;i<=n;++i)bit[i]=bit[i>>1]+1;
for(int i=1;i<=n;++i)max[i][0]=i;
for(int j=1;j<=bit[n];++j){
for(int i=1;i+(1<<j)-1<=n;++i){
max[i][j]=slt(max[i][j-1],max[i+(1<<(j-1))][j-1]);
}
}
}
inline int rmq(int l,int r){
int i=bit[r-l+1];
return slt(max[l][i],max[r-(1<<i)+1][i]);
}
};
char str[max_N+21],tmp[max_N+21];
int n,right[max_N+21];
Kmp<max_N+21>kmp;
SparseTable<max_N+21,17>st;
int ans;
std::vector<std::pair<int,int>>vec;
inline int query(int L,int R){
int l=1,r=R-L+1;
r=(r&1)?(r+1)/2:r/2;
int ans=-1;
while(l<=r){
int mid=(l+r)>>1;
int tmp=st.rmq(L+mid-1,R-mid+1);
if(manacher.r[0][tmp]>=mid){
ans=tmp;
l=mid+1;
}
else{
r=mid-1;
}
}
return ans;
}
inline void solve(){
int x=st.rmq(1,n);
ans=manacher.r[0][x]*2-1;
vec.push_back({x-manacher.r[0][x]+1,x+manacher.r[0][x]-1});
//printf("%d %d\n",x,ans);
for(int i=1;i<=n;++i){
if(right[i]<=2*i)continue;
int middle=query(i+1,right[i]-i);
int R=manacher.r[0][middle];
R=std::min(R,std::min(middle-i,right[i]-i-middle+1));
int ml=middle-R+1,mr=middle+R-1;
int len=i*2+(mr-ml+1);
if(len>ans){
ans=len;
vec.clear();
vec.push_back({right[i]-i+1,right[i]});
vec.push_back({ml,mr});
vec.push_back({1,i});
}
}
}
int main(){
scanf("%s",str+1);
n=strlen(str+1);
strcpy(tmp+1,str+1);
std::reverse(str+1,str+1+n);
kmp.matching(tmp,n,str,n,right);
for(int i=1;i<=n;++i)if(!right[i])right[i]=i;
manacher.build(str,n,0);
manacher.build(str,n,1);
st.init(n);
solve();
printf("%d\n",(int)vec.size());
for(auto&x:vec)printf("%d %d\n",n-x.second+1,x.second-x.first+1);
return 0;
}Problem K. A Text Problem
检验模板：SuffixArray
题目大意：
定义字符串\(A\)在字符串\(B\)中的位置\(i\)满足允许错一次的匹配成功当且仅当存在将\(A\)中某一个位置的字符替换后得到的字符串\(A^{'}\)(可能替换后\(A=A^{'}\))满足\(\forall j\in [0,|A^{'}|),S[i+j]=A^{'}[j]\)。
给出字符串\(S\)，和若干次询问，每次询问给出一个字符串\(T\)，满足\(|S|\ge|T|\)，问\(T\)能在\(S\)中的多少个位置满足允许错一次的匹配成功。
保证\(|S|\le2\times10^5,\sum|T|\le2\times10^5\)。
题解：
令\(S\)的长度为\(n\)，\(T\)的长度为\(m\)。
先求出\(S\)的后缀数组\(A\)，及其名次数组\(posA\)，然后对于\(T\)的每个后缀\(T[i\cdots (m-1)]\)：
- 找到最小的\(k\)满足\(\displaystyle S[A[k]\cdots(n-1)] \ge T[ i...(m-1)]\)，记为\(a1[i]\)。
- 再找到最大的\(k\)满足\(\displaystyle S[A[k]\cdots\min(n-1,A[k]+m-i-1)] \le T[i\cdots(m-1)]\)，记为\(a2[i]\)。
显然有\(\displaystyle S[j\cdots (j+m-i-1)]=T[i\cdots(m-1)]\)当且仅当\(\displaystyle a1[i]\le posA[j] \le a2[i]\)。
同理，我们求出\(S\)的反串\(S1\)的后缀数组\(A1\)，记\(B[i]=n-A1[i]\)，令\(posB[B[i]]=i\)。
即\(\displaystyle reverse(S[0\cdots(B[i]-1)])\)是字典序第\(i\)小的反前缀。
然后对于\(T\)的每个反前缀\(\displaystyle reverse(T[0\cdots i])\)：
- 找到最小的\(k\)满足\(\displaystyle reverse(S[0\cdots(B[k]-1)]) \ge reverse(T[0\cdots i])\)，记为\(b1[i]\)。
- 找到最大的\(k\)满足\(\displaystyle reverse(S[\max(0,B[k]-1-i)\cdots(B[k]-1)]) \le reverse(T[0\cdots i])\)，记为\(b2[i]\)。
显然有\(\displaystyle S[(j-i)\cdots j] = T[0\cdots i]\)当且仅当\(\displaystyle b1[i]\le posB[j+1] \le b2[i]\)。
因此，枚举\(T\)和\(S\)在匹配时允许出错的位置分别为\(i\)和\(j\)，则匹配成功的充要条件为 \[ \displaystyle S[(j-i)\cdots(j-1)]=T[0\cdots(i-1)] \land S[(j+1)\cdots(j-i+m-1)]=T[(i+1)\cdots(m-1)] \] 即： \[ \displaystyle a1[i+1]\le posA[i+1] \le a2[i+1] \land b1[i-1]\le posB[i] \le b2[i-1] \] 这样就成功将原问题转化为了二维数点问题。
但是这样做还有一点小bug：如果\(T\)可以不允许失败地在\(S\)中匹配成功，则会重复计算这一部分的答案。
解决方法很简单，肯定是每次 严格成功的匹配被计算了\(m\)次，答案减去\((b2[m-1]-b1[m-1]+1)\times(m-1)\)即可。
因此最终的答案为 \[ \displaystyle ans = \sum\limits_{i=0}^{m-1} count(a1[i+1],a2[i+1],b1[i-1],b2[i-1]) - [b1[m-1]\le b2[m-1]]\times(b2[m-1]-b1[m-1]+1)\times(m-1) \] 二维数点的部分可以预处理主席树在线回答询问，时间复杂度\(O(n\log{n}+\sum |T|\log{n})\)。
那么现在问题只剩下如何去求\(a1,a2,b1,b2\)了。
我们可以倒着求\(a1\)和\(a2\)，显然有\(a1[m]=0,a2[m]=n\)。
假如我们已知了\(a1[i+1]\cdots a1[m]\)和\(a2[i+1]\cdots a2[m]\)，那么：
- \(\displaystyle S[A[k]\cdots(n-1)] < T[ i...(m-1)]\)等价于\(\displaystyle A[k]=n \lor S[A[k]]<T[i] \lor (S[A[k]]=T[i]\land posA[A[k]+1]<a1[i+1])\)
- \(\displaystyle S[A[k]\cdots(n-1)] > T[ i...(m-1)]\)等价于\(\displaystyle A[k]<n\land (S[A[k]]>T[i] \lor (S[A[k]]=T[i]\land posA[A[k]+1]>a2[i+1]))\)
因此，我们可以二分求解，时间复杂度为\(O(n\log{n})\)。
同理我们可以顺序求解\(b1\)和\(b2\)，显然有\(b1[-1]=0,b2[-1]=n\)。
假如我们已知了\(b1[-1]\cdots b1[i-1]\)和\(b2[-1]\cdots b2[i-1]\)，那么：
- \(\displaystyle reverse(S[0\cdots(B[k]-1)]) < reverse(T[0\cdots i])\)等价于$k=0 S[B[k]-1]<T[i] (S[B[k]-1]=T[i]posB[B[k]-1]<b1[i-1]) $
- \(\displaystyle reverse(S[0\cdots(B[k]-1)]) > reverse(T[0\cdots i])\)等价于\(\displaystyle k>0 \land (S[B[k]-1]>T[i] \lor (S[B[k]-1]=T[i]\land posB[B[k]-1]>b1[i-1]) )\)
同样，我们可以二分求解，时间复杂度为\(O(n\log{n})\)。
至此，我们就解决了这个问题，整个算法时间复杂度为\(O((\sum|S|+\sum|T|)\log{|S|})\)。
#include <bits/stdc++.h>
#define all_of(x) (x).begin(),(x).end()
using ll = long long;
const int max_N=int(2e5)+21;
namespace SuffixArray{
int sa[max_N];
int tmp[max_N],cnt[max_N],bc[max_N];
inline void build(char*s,int n){
register int i,T,sigma;
for(i=0;i<n;++i)sa[i]=i;
std::sort(sa,sa+n,[&](int a,int b){return s[a]<s[b];});
for(i=1,bc[sa[0]]=1;i<n;++i)bc[sa[i]]=bc[sa[i-1]]+(s[sa[i-1]]<s[sa[i]]);
for(T=1;(sigma=bc[sa[n-1]])<n;T<<=1){
auto cmp=[&s,&T,&n](const int&a,const int&b){
if(bc[a]!=bc[b])return bc[a]<bc[b];
return (a+T>=n||b+T>=n)?a>b:bc[a+T]<bc[b+T];
};
for(i=0;i<=sigma;++i)cnt[i]=0;
for(i=0;i<n;++i)++cnt[(i+T>=n)?0:bc[i+T]];
for(i=1;i<=sigma;++i)cnt[i]+=cnt[i-1];
for(i=n-1;~i;--i)tmp[--cnt[(sa[i]+T>=n)?0:bc[sa[i]+T]]]=sa[i];
for(i=0;i<=sigma;++i)cnt[i]=0;
for(i=0;i<n;++i)++cnt[bc[i]];
for(i=1;i<=sigma;++i)cnt[i]+=cnt[i-1];
for(i=n-1;~i;--i)sa[--cnt[bc[tmp[i]]]]=tmp[i];
for(i=1,tmp[sa[0]]=1;i<n;++i)tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);
memcpy(bc,tmp,sizeof(int)*n);
}
}
};
int n;
int A[max_N],B[max_N],posA[max_N],posB[max_N];
int a1[max_N],a2[max_N],b1[max_N],b2[max_N];
char s[max_N],q[max_N];
using star=struct node*;
struct node{
int sum; star l,r;
}pool[max_N*20];
star rt[max_N],tail,null;
void build(star&x,star y,int l,int r,int t){
x=tail++,*x=*y,++x->sum;
if(l==r)return; int mid=(l+r)>>1;
if(t>mid)build(x->r,y->r,mid+1,r,t);
else build(x->l,y->l,l,mid,t);
}
inline ll count(int a,int b,int c,int d){
// count number of points in [a,b] x [c,d]
std::function<int(star,int,int)>
calc=[&calc,&c,&d](star x,int l,int r){
if(x==null||(c<=l&&r<=d))return x->sum;
int mid=(l+r)>>1,res=0;
if(c<=mid)res+=calc(x->l,l,mid);
if(d>mid) res+=calc(x->r,mid+1,r);
return res;
};
int res=calc(rt[b],0,n);
if(a)res-=calc(rt[a-1],0,n);
return res;
}
inline void init(){
register int i;
scanf("%s",s);
n=strlen(s);
// A[i] is the ith smallest suffix: s[A[i]...n-1]
SuffixArray::build(s,n);
for(A[i=0]=n;i<n;++i)A[i+1]=SuffixArray::sa[i];
std::reverse(s,s+n);
// B[i] is the ith smallest rev_prefix: rev(s[0...B[i]-1])
SuffixArray::build(s,n);
for(B[i=0]=0;i<n;++i)B[i+1]=n-SuffixArray::sa[i];
std::reverse(s,s+n);
for(i=0;i<=n;++i)posA[A[i]]=posB[B[i]]=i;
// maintain 2d-points (posA[i+1],posB[i])
tail=pool;
null=tail++,null->l=null->r=null,null->sum=0;
star last=null;
for(int i=0;i<=n;++i){
if(A[i])build(last,last,0,n,posB[A[i]-1]);
rt[i]=last;
}
}
inline void solve(){
int Q,m,lo,hi,mi;
scanf("%d",&Q);
while(Q--){
scanf("%s",q);
m=strlen(q);
a1[m]=0,a2[m]=n;
for(int i=m-1;~i;--i){
// binary-searching 1:
// a1[i] is the smallest k
// s.t. s[A[k]...n-1] >= q[i...m-1]
lo=0,hi=n+1;
while(lo<hi){
auto check=[&i](const int&mi){
int tmp=A[mi]; if(tmp==n)return true;
return s[tmp]<q[i]||(s[tmp]==q[i]&&posA[tmp+1]<a1[i+1]);
};
if(check(mi=(lo+hi)>>1))lo=mi+1; else hi=mi;
}
a1[i]=lo;
// binary-searching 2:
// a2[i] is the largest k
// s.t. s[A[k]...min(n,A[k]+(m-i))-1] <= q[i...m-1]
lo=0,hi=n;
while(lo<hi){
auto check=[&i](const int&mi){
int tmp=A[mi]; if(tmp==n)return false;
return s[tmp]>q[i]||(s[tmp]==q[i]&&posA[tmp+1]>a2[i+1]);
};
if(check(mi=(lo+hi+1)>>1))hi=mi-1; else lo=mi;
}
a2[i]=lo;
}
ll ans=0; int b1=0,b2=n;
for(int i=0;i<m&&b1<=b2;++i){
if(a1[i+1]<=a2[i+1])ans+=count(a1[i+1],a2[i+1],b1,b2);
// binary-searching 3:
// b1 is the smallest k
// s.t. rev(s[0...B[k]-1]) >= rev(q[0...i])
lo=0,hi=n+1;
while(lo<hi){
auto check=[&i,&b1](const int&mi){
int tmp=B[mi]; if(!tmp)return true;
return s[tmp-1]<q[i]||(s[tmp-1]==q[i]&&posB[tmp-1]<b1);
};
if(check(mi=(lo+hi)>>1))lo=mi+1; else hi=mi;
}
b1=lo;
// binary-searching 4:
// b2 is the largest k
// s.t. rev(s[max(0,B[k]-1-i)...B[k]-1]) <= rev(q[0...i]);
lo=0,hi=n;
while(lo<hi){
auto check=[&i,&b2](const int&mi){
int tmp=B[mi]; if(!tmp)return false;
return s[tmp-1]>q[i]||(s[tmp-1]==q[i]&&posB[tmp-1]>b2);
};
if(check(mi=(lo+hi+1)>>1))hi=mi-1; else lo=mi;
}
b2=lo;
}
if(b1<=b2)ans-=1ll*(b2-b1+1)*(m-1);
// ans = sigma i in [0,m) count(a1[i+1],a2[i+1],b1[i-1],b2[i-1])
// - [b1[m-1] <= b2[m-1]] * (b2[m-1]-b1[m-1]+1) * (m-1)
printf("%lld\n",ans);
}
}
int main(){
int T; scanf("%d",&T);
while(T--)init(),solve();
return 0;
}