题解 P4341 【[BJWC2010]外星联络】
Jμdge
2018-07-04 14:40:13
## 多久没写题解了...
这道题其实大体框架就是build_sa 然后build_height.
最后用height求解。
另外解释一下最后的操作：
1. 按照排名用i枚举后缀子串(排名为1的子串可以不枚举)
2. 用j枚举出现新子串的长度,从h[i-1]+1 到 h[i]
3. 用k向下记录长度超过j的子串,直至碰到了h[k]小于j的情况,此时k-i+1就是当前长度为j的子串在原串中出现的次数
基本思路和楼下的bzt大佬一样,但是我的code有一点小优化可以让80ms的时间减成0ms。其实这个思路很朴素.
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
const int M=31000;
const int inf=1e9;
inline int cread() { //日常字符读优
char c=getchar();
while(!isdigit(c))
c=getchar();
return c;
}
char s[M];
int n,m,k,p,mx;
int a[M],b[M],c[M];
int sa[M],rk[M],hi[M],f[M];
inline int cmpe(int i,int j) { //get sa 子模板
int aa=i+k>n ? -1 : b[i+k],
bb=j+k>n ? -1 : b[j+k];
return (b[i]!=b[j] || aa!=bb);
}
inline void build_sa() { //get sa 模板
for(int i=1; i<=m; ++i) c[i]=0;
for(int i=1; i<=n; ++i) ++c[a[i]=s[i]];
for(int i=2; i<=m; ++i) c[i]+=c[i-1];
for(int i=n; i; --i) sa[c[a[i]]--]=i;
for(k=1,p=0; k<=n; k<<=1,m=p,p=0) {
for(int i=n-k+1; i<=n; ++i) b[++p]=i;
for(int i=1; i<=n; ++i) if(sa[i]>k)
b[++p]=sa[i]-k;
for(int i=1; i<=m; ++i) c[i]=0;
for(int i=1; i<=n; ++i) ++c[a[i]];
for(int i=2; i<=m; ++i) c[i]+=c[i-1];
for(int i=n; i; --i) sa[c[a[b[i]]]--]=b[i];
swap(a , b), a[sa[1]]=1, p=1;
for(int i=2; i<=n; ++i)
a[sa[i]]=cmpe(sa[i-1],sa[i])? ++p : p;
if(p==n) break;
}
for(int i=1; i<=n; ++i)
rk[sa[i]]=i;
}
inline void build_hi() { //get height 模板
k=0, hi[1]=0;
for(int i=1; i<=n; ++i)if(rk[i]>1) {
int j=sa[rk[i]-1];
if(k) --k;
while(i+k<=n && j+k<=n && s[i+k]==s[j+k])
++k;
hi[rk[i]]=k;
}
}
int main() {
scanf("%d",&n), m=127;
for(int i=1; i<=n; ++i)
s[i]=cread();
build_sa(), build_hi();
for(int i=2; i<=n; ++i) {
//按排名枚举子串(第一个舍去)
for(int j=hi[i-1]+1; j<=hi[i]; ++j) {
//j初始值为hi[i-1]+1,即排名为i-1的子串lcp,避免重复计算,
//然后j要<=hi[i],即当前子串串长
int k=i;
while(hi[k]>=j) ++k;
//寻找lcp值>=j的子串最后一次出现的位置
printf("%d\n",k-i+1);
}
}
return 0;
}
```