你喜欢字符串。有人送了你一个仅含小写字母的字符串。
由于你是一名优秀的 ????er，所以你决定对这个字符串展开研究。
定义两个字符串是相似的，当且仅当存在至多一个 ?? ，使得这两个字符串中只有第 ?? 个字母不同。
你取出了这个字符串中所有长度为m 的子串。你想知道，对于每个长度为 m 的子串，有多少个其它长度为 m 的子串与它相似。
n<=10^5 1<=m<=n
dh牛逼，不接受反驳
省选前的SA复习
若ij相似，则lcp+lcs>=m-1
建出前缀&后缀SA，在前缀的height上分治
每次按min(hi)分开，枚举较小的那一边来搞
因为lcp确定了，所以等于找lcs>=m-1-lcp，对应到后缀height是一段区间
那么线段树维护后缀height，小的那边可以直接查询
对于大的那边，在处理每个小的的时候在线段树上打tag最后查询
因为tag的意义是对当前线段树的修改，所以合并时先下传再合并
想是一回事，打起来又是另一回事了
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define file
using namespace std;
int D2[100001],Rk[100001],p[17],P[100001],ans[100001],n,m,i,j,k,l,id;
char ch;
vector<int> D[100001];
struct String{
int rk[100002],sa[100001],hi[100001],h[100001],a[100001],rmq[100001][17],Rmq[100001][17],x,y;
void init()
{
fo(i,1,n) rk[i]=a[i];
l=1;
while (l<n)
{
k=0;
fo(i,1,n) D[rk[min(i+l,n+1)]].push_back(i);
fo(i,0,n) while (!D[i].empty()) D2[++k]=D[i].back(),D[i].pop_back();
fd(i,n,1) D[rk[D2[i]]].push_back(D2[i]);
memcpy(Rk,rk,(n+1)*4);k=0;
fo(i,0,n)
{
x=y=0;
while (!D[i].empty())
{
id=D[i].back();k+=x!=Rk[id] || y!=Rk[min(id+l,n+1)];x=Rk[id],y=Rk[min(id+l,n+1)];
rk[id]=k;D[i].pop_back();
}
}
l*=2;
}
fo(i,1,n) sa[rk[i]]=i;
fo(i,1,n)
if (rk[i]<n)
{
h[i]=min(max(h[i-1]-1,0),min(n-i+1,n-sa[rk[i]+1]+1));
while (h[i]<min(n-i+1,n-sa[rk[i]+1]+1) && a[i+h[i]]==a[sa[rk[i]+1]+h[i]]) ++h[i];
}
else h[i]=0;
fo(i,1,n) if (rk[i]<n) hi[rk[i]]=h[i];
// ---
fo(i,1,n-1) rmq[i][0]=hi[i],Rmq[i][0]=i;
fo(i,1,16)
{
fo(j,1,(n-1)-p[i]+1)
if (rmq[j][i-1]<rmq[j+p[i-1]][i-1])
rmq[j][i]=rmq[j][i-1],Rmq[j][i]=Rmq[j][i-1];
else
rmq[j][i]=rmq[j+p[i-1]][i-1],Rmq[j][i]=Rmq[j+p[i-1]][i-1];
}
}
pair<int,int> get(int x,int y) //after sorting
{
int s1,s2;
if (x==y) return pair<int,int>(n-sa[x]+1,0);
--y;
if (rmq[x][P[y-x+1]]<rmq[y-p[P[y-x+1]]+1][P[y-x+1]])
s1=rmq[x][P[y-x+1]],s2=Rmq[x][P[y-x+1]];
else
s1=rmq[y-p[P[y-x+1]]+1][P[y-x+1]],s2=Rmq[y-p[P[y-x+1]]+1][P[y-x+1]];
return pair<int,int>(s1,s2);
}
} a,b;
struct tree{
int tr[7000001][3],Tr[7000001],len;
void New(int t,int x) {if (!tr[t][x]) tr[t][x]=++len;}
void down(int t,int l,int r)
{
if (Tr[t])
{
if (l<r) Tr[tr[t][0]]+=Tr[t],Tr[tr[t][1]]+=Tr[t];
else {if (b.sa[l]<=n-m+1) ans[n-b.sa[l]+1-m+1]+=Tr[t];}
Tr[t]=0;
}
}
void change(int t,int l,int r,int x)
{
int mid=(l+r)/2;
++tr[t][2];
if (l==r) return;
if (x<=mid) New(t,0),change(tr[t][0],l,mid,x);
else New(t,1),change(tr[t][1],mid+1,r,x);
}
void Change(int t,int l,int r,int x,int y)
{
int mid=(l+r)/2;
if (x<=l && r<=y) {++Tr[t];return;}
if (x<=mid && tr[t][0]) Change(tr[t][0],l,mid,x,y);
if (mid<y && tr[t][1]) Change(tr[t][1],mid+1,r,x,y);
}
int find(int t,int l,int r,int x,int y)
{
int mid=(l+r)/2,ans=0;
if (x<=l && r<=y) return tr[t][2];
if (x<=mid && tr[t][0]) ans+=find(tr[t][0],l,mid,x,y);
if (mid<y && tr[t][1]) ans+=find(tr[t][1],mid+1,r,x,y);
return ans;
}
void merge(int t1,int t2,int l,int r)
{
int mid=(l+r)/2;
down(t1,l,r),down(t2,l,r);
if (l==r) {tr[t1][2]+=tr[t2][2];return;}
if (tr[t1][0] && tr[t2][0])
merge(tr[t1][0],tr[t2][0],l,mid);
else
if (tr[t2][0])
tr[t1][0]=tr[t2][0];
if (tr[t1][1] && tr[t2][1])
merge(tr[t1][1],tr[t2][1],l,mid);
else
if (tr[t2][1])
tr[t1][1]=tr[t2][1];
tr[t1][2]=tr[tr[t1][0]][2]+tr[tr[t1][1]][2];
}
void dfs(int t,int l,int r)
{
int mid=(l+r)/2;
down(t,l,r);
if (l==r) return;
if (tr[t][0]) dfs(tr[t][0],l,mid);
if (tr[t][1]) dfs(tr[t][1],mid+1,r);
}
} tr;
void swap(int &x,int &y) {int z=x;x=y;y=z;}
int work(int x,int y)
{
if (x==y) {if (a.sa[x]<=n-m+1) tr.change(x,1,n,b.rk[n-a.sa[x]+1-m+1]); return x;}
pair<int,int> S=a.get(x,y);
int s1=S.first,s2=S.second,mid,i,j,k,l,r,L,R,t1=work(x,s2),t2=work(s2+1,y),st,ed;
if ((s2-x+1)*2<=y-x+1)
st=x,ed=s2;
else
st=s2+1,ed=y,swap(t1,t2);
fo(i,st,ed)
if (a.sa[i]<=n-m+1)
{
l=1;r=b.rk[n-a.sa[i]+1-m+1];
while (l<r)
{
mid=(l+r)/2;
if (b.get(mid,b.rk[n-a.sa[i]+1-m+1]).first>=m-1-s1)
r=mid; else l=mid+1;
}
L=l;
l=b.rk[n-a.sa[i]+1-m+1];r=n;
while (l<r)
{
mid=(l+r)/2;
if (b.get(b.rk[n-a.sa[i]+1-m+1],mid).first>=m-1-s1)
l=mid+1; else r=mid;
}
if (!(b.get(b.rk[n-a.sa[i]+1-m+1],l).first>=m-1-s1)) --l;
R=l;
ans[a.sa[i]]+=tr.find(t2,1,n,L,R);
tr.Change(t2,1,n,L,R);
}
tr.merge(t1,t2,1,n);
return t1;
}
int main()
{
freopen("string.in","r",stdin);
#ifdef file
freopen("string.out","w",stdout);
#endif
p[0]=1;fo(i,1,16) p[i]=p[i-1]*2;
fo(i,1,100000) P[i]=floor(log2(i));
scanf("%d%d",&n,&m);
fo(i,1,n)
{
ch=getchar();
while (ch<‘a‘ || ch>‘z‘) ch=getchar();
a.a[i]=ch-‘a‘+1;
}
fd(i,n,1) b.a[i]=a.a[n-i+1];
a.init();b.init();
tr.len=n;
tr.dfs(work(1,n),1,n);
fo(i,1,n-m+1) printf("%d ",ans[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}
原文：https://www.cnblogs.com/gmh77/p/12790743.html