LINK
題意
給出
n
n
n個串,求每個串有多少
[
l
,
r
]
[l,r]
[l,r]的區間
使得這段區間在這
n個串中的至少
k
k
k個串包含。
把
n個串穿起來,中間用不同的字元連接配接
對于串
s
s
s如何計算答案…
考慮對串
s的每個字尾計算一遍答案
相當于固定了左端點
l
l,要求最大的右端點
r
r
相當于找到
k個來自不同字元串的字尾(包括串s的字尾),使得它們的
c
p
lcp
lcp最大
那麼串
s的答案加上
lcp
于是我們按照
a
sa
sa的順序尺取一些恰好包括
k個不同串的區間
尺取的規則是對于每個
l,尺取一個
r滿足
[l,r]剛好有
k個不同子串
區間最小值
lcp就是貢獻,拿這個
lcp給這段區間每個點取
m
x
max
max
但是其他點怎麼辦??這段區間的貢獻還可以往左往右擴充啊,隻不過
lcp會變小
很可能前面尺取的區間
lcp,還不如現在這個區間的
lcp往左邊擴充
或者甚至後面的某些點根本沒有被長度為
k的包含進來
我們這樣,讓每個區間的貢獻往右擴充,這樣就不需要考慮往左邊擴充
想一下一個區間的
lcp是
x
x,往右邊擴充
lcp變成
i
(
h
e
g
t
)
min(lcp,height[i])
min(lcp,height[i])
是以我們最後做一個字首最大值即可,也就是
m
x
[
i
]
=
a
(
,
n
−
1
h
e
g
t
)
mx[i]=max(mx[i],min(mx[i-1],height[i]))
mx[i]=max(mx[i],min(mx[i−1],height[i]))
因為和上一個字尾最長是
height[i]
height[i],是以需要取
min
min
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
char a[maxn];
int s[maxn],x[maxn],y[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn],n,m;
void get_sa(int n)
{
// m = 30000;
for(int i=1;i<=n;i++) ++c[x[i]=s[i]];
for(int i=2;i<=m;i++) c[i] += c[i-1];
for(int i=n;i>=1;i--) sa[c[x[i]]--] = i;
for(int k=1;k<=n;k<<=1)
{
int num = 0;
for(int i=n-k+1;i<=n;i++) y[++num] = i;
for(int i=1;i<=n;i++) if( sa[i]>k ) y[++num] = sa[i]-k;
for(int i=0;i<=m;i++) c[i] = 0;
for(int i=1;i<=n;i++) ++c[x[i]];
for(int i=1;i<=m;i++) c[i] += c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x,y);
x[sa[1]] = 1, num = 1;
for(int i=2;i<=n;i++)
x[sa[i]] = ( y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] )?num:++num;
if( num==n ) break;
m = num;
}
for(int i=1;i<=n;i++) rk[sa[i]] = i;
for(int k=0,i=1;i<=n;i++)
{
if( rk[i]==1 ) continue;
if( k ) k--;
int j = sa[rk[i]-1];
while( i+k<=n&&j+k<=n&&s[i+k]==s[j+k] ) k++;
height[rk[i]] = k;
}
}
int vis[maxn],now,id[maxn],mx[maxn];//尺取
void del(int l,int &now)
{
vis[id[sa[l]]]--;
if( vis[id[sa[l]]]==0 ) now--;
}
void add(int r,int &now)
{
vis[id[sa[r]]]++;
if( vis[id[sa[r]]]==1 ) now++;
}
int st[maxn][22],top,k;
void init()
{
for(int i=1;i<=top;i++) st[i][0] = height[i];
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=top;j++)
st[j][i] = min( st[j][i-1],st[j+(1<<(i-1))][i-1] );
}
int get(int l,int r)
{
int k = log2(r-l+1);
return min( st[l][k],st[r-(1<<k)+1][k] );
}
ll ans[maxn];
int main()
{
cin >> n >> k;
if(k==1)//特判k=1的情況
{
for(long long i=1;i<=n;i++)
{
scanf("%s",a+1);
long long len=strlen(a+1);
printf("%lld ",(len*(len+1))>>1);
}
return 0;
}
m = n+200;
for(int i=1;i<=n;i++)
{
scanf("%s",a+1); int len = strlen( a+1 );
for(int j=1;j<=len;j++) s[++top] = a[j]+n,id[top] = i;
s[++top] = i;
}
get_sa(top); init();
int now = 0;
for(int r=n,l=n+1;l<=top;l++)
{
if( l>n+1 ) del(l-1,now);
while( r<l ) add(++r,now);
while( r<top&&now<k ) add(++r,now);
if( now<k ) break;
//求區間最小值
int lcp = get(l+1,r);
//更新這段區間的每個點
for(int j=l;j<=r;j++) mx[j] = max( mx[j],lcp );
}
for(int i=n+2;i<=top;i++) mx[i] = max( mx[i],min( mx[i-1],height[i] ) );
for(int i=n+1;i<=top;i++) ans[id[sa[i]]] += mx[i];
for(int i=1;i<=n;i++) cout << ans[i] << " ";
}
還是類似的做法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
char a[maxn];
int s[maxn],x[maxn],y[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn],n,m;
void get_sa(int n)
{
m = 300;
for(int i=1;i<=n;i++) ++c[x[i]=s[i]];
for(int i=2;i<=m;i++) c[i] += c[i-1];
for(int i=n;i>=1;i--) sa[c[x[i]]--] = i;
for(int k=1;k<=n;k<<=1)
{
int num = 0;
for(int i=n-k+1;i<=n;i++) y[++num] = i;
for(int i=1;i<=n;i++) if( sa[i]>k ) y[++num] = sa[i]-k;
for(int i=1;i<=m;i++) c[i] = 0;
for(int i=1;i<=n;i++) ++c[x[i]];
for(int i=2;i<=m;i++) c[i] += c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x,y);
x[sa[1]] = 1, num = 1;
for(int i=2;i<=n;i++)
x[sa[i]] = ( y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] )?num:++num;
if( num==n ) break;
m = num;
}
for(int i=1;i<=n;i++) rk[sa[i]] = i;
for(int k=0,i=1;i<=n;i++)
{
if( rk[i]==1 ) continue;
if( k ) k--;
int j = sa[rk[i]-1];
while( i+k<=n&&j+k<=n&&s[i+k]==s[j+k] ) k++;
height[rk[i]] = k;
}
}
int vis[maxn],now,id[maxn],mx[maxn];//尺取
void del(int l,int &now)
{
vis[id[sa[l]]]--;
if( vis[id[sa[l]]]==0 ) now--;
}
void add(int r,int &now)
{
vis[id[sa[r]]]++;
if( vis[id[sa[r]]]==1 ) now++;
}
int st[maxn][22],top,k;
void init()
{
for(int i=1;i<=top;i++) st[i][0] = height[i];
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=top;j++)
st[j][i] = min( st[j][i-1],st[j+(1<<(i-1))][i-1] );
}
int get(int l,int r)
{
int k = log2(r-l+1);
return min( st[l][k],st[r-(1<<k)+1][k] );
}
ll ans[maxn];
int main()
{
cin >> n >> k;
for(int i=1;i<=n;i++)
{
scanf("%s",a+1); int len = strlen( a+1 );
for(int j=1;j<=len;j++) s[++top] = a[j]-'a'+n,id[top] = i;
s[++top] = i;
}
get_sa(top); init();
int now = 0;
for(int l=n+1,r=n+1;r<=top;r++)
{
add(r,now);//加入右端點
while( now>=k )
{
if( now==k )
{
int lcp = get(l+1,r);
cout << l << " " << r << " " << lcp << endl;
for(int j=l;j<=r;j++) mx[j] = max( mx[j],lcp );
}
if( vis[id[sa[l]]]==1 )
{
if( now==k ) break;
now--;
}
vis[id[sa[l]]]--; l++;
}
}
// for(int i=n+2;i<=top;i++) mx[i] = max( mx[i],min( mx[i-1],height[i] ) );
for(int i=n+1;i<=top;i++) ans[id[sa[i]]] += mx[i];
for(int i=1;i<=n;i++) cout << ans[i] << " ";
}