题目传送门：http://pan.baidu.com/s/1qYPBdpU
数据生成器：http://paste.ubuntu.com/19351549/
OJ传送门：http://oi.cdshishi.net:8080/Problem/1719
这道题目，一看，SA的板题嘛！于是很高兴的码了SA
码完之后一对拍，发现，好像常数很大的样子，然而一看数据范围，嗯，一定是O(nlogn)的复杂度
结果，又被卡常了QAQ
说一说SA的做法：
首先在SA上二分，搞出len
然后再次在SA上二分，搞出最小的标号
然后总体复杂度O(6*n*log(n))，于是T了一个点QAQ
再来说一说SAM的做法（QJC说：这不是SAM的一眼题吗QAQ）
两个字串的lcp，是fail树上的lca，于是考虑在lca上染色的话，O(n)即可
另外，此题不是要求的不是后缀关系，是前缀关系，于是我们倒着建即可
SA版本：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1000000+9;
const int SGZ = 26;
const int INF = 100000000;
char pat[MAXN];
int n;
namespace Suffix_Array{
#define SA Suffix_Array
int height[MAXN],sa[MAXN],t1[MAXN],t2[MAXN],bot[MAXN];
int *tmp,*rank,m,K[MAXN],LEN[MAXN];
inline void ST_Advance(){
for (int i=1,k,len;i<=n;i++) {
k = 0, len = 1;
while (len < i) len *= 2, k++;
K[i] = k; LEN[i] = len;
}
}
struct Sparse_Table{
int MN[MAXN][20];
inline void init(int *arr){
for (int i=1;i<=n;i++) MN[i][0] = arr[i];
for (int k=1,lim=2;k<=19;k++,lim=1<<k) for (int i=1;i<=n-lim+1;i++)
MN[i][k] = min(MN[i][k-1], MN[i+(1<<(k-1))][k-1]);
}
inline int query(int a, int b){
if (a > b) swap(a, b);
int sta=(b-a+2)/2,k=K[sta],len=LEN[sta];
return min(MN[a][k], MN[b-len+1][k]);
}
}ST_num,ST_hei;
inline void GetHeight(){
for (int i=1;i<=n;i++) if (rank[i] > 1) {
int sta = max(0, height[rank[i-1]]-1);
int p1 = sta + i, p2 = sta + sa[rank[i]-1];
while (pat[p1++] == pat[p2++]) sta++;
height[rank[i]] = sta;
}
}
inline void build(){
tmp = t1, rank = t2;
n = strlen(pat+1); m = SGZ;
for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+1]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++)
if (tmp[sa[i]] != tmp[sa[i-1]]) rank[sa[i]] = ++m;
else rank[sa[i]] = m;
for (int k=1;k<=n;k*=2) { int T = 0;
for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
for (int i=1;i<=m;i++) bot[i] = 0;
for (int i=1;i<=n;i++) bot[rank[i]]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
swap(tmp, rank); rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++)
if (tmp[sa[i]] != tmp[sa[i-1]] || tmp[sa[i]+k] != tmp[sa[i-1]+k]) rank[sa[i]] = ++m;
else rank[sa[i]] = m;
if (m >= n) break;
}
GetHeight();
ST_Advance();
ST_num.init(sa);
ST_hei.init(height);
}
inline void solve(){
for (int w=1,tag=0;w<n;tag=0) {
int mid, l = 1, r = rank[w] - 1, len = 0, ans = 0;
while (l <= r) {
mid = (l + r) / 2;
if (ST_num.query(rank[w]-mid,rank[w]-1) < w) r = mid-1, len = mid;
else l = mid+1;
}
if (len) ans = ST_hei.query(rank[w]-len+1, rank[w]);
l = 1; r = n - rank[w]; len = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (ST_num.query(rank[w]+1, rank[w]+mid) < w) r = mid-1, len = mid;
else l = mid+1;
}
if (len) ans = max(ans, ST_hei.query(rank[w]+1, rank[w]+len));
if (ans) {
printf("%d ",ans); tag = ans;
l = 1; r = rank[w]; len = 0; ans = INF;
while (l <= r) {
mid = (l + r) / 2;
if (ST_hei.query(rank[w], rank[w]-mid+1) >= tag) l = mid+1, len = mid;
else r = mid-1;
}
if (len) ans = ST_num.query(rank[w]-len,rank[w]-1);
l = 1; r = n-rank[w]; len = 0;
while (l <= r) {
mid = (l + r) / 2;
if (ST_hei.query(rank[w]+1, rank[w] + mid) >= tag) l = mid+1, len = mid;
else r = mid-1;
}
if (len) ans = min(ans, ST_num.query(rank[w]+1, rank[w]+len));
printf("%d ",ans-1); w += tag;
} else {
printf("%d %d ",-1,(int)pat[w]);
w ++;
}
}
}
};
int main(){
freopen("encrypt.in","r",stdin);
freopen("encrypt.out","w",stdout);
scanf("%s",pat+1);
SA::build();
SA::solve();
return 0;
}
SAM版本：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1000000+9;
const int SGZ = 27;
char pat[MAXN];
int n;
namespace Suffix_Automaton{
#define SAM Suffix_Automaton
int ch[MAXN][SGZ],fail[MAXN],tag[MAXN],W=1;
int cnt,last,dep[MAXN],pos[MAXN];
inline void extend(int i, int c){
int w = last; dep[pos[i]=last=++cnt] = dep[w]+1;
while (w && !ch[w]) ch[w] = last, w = fail[w];
if (!ch[w]) fail[last] = 1;
else {
int nw = ch[w];
if (dep[nw] == dep[w] + 1) fail[last] = nw;
else {
int nnw = ++cnt; dep[nnw] = dep[w] + 1;
memcpy(ch[nnw],ch[nw],sizeof(ch[nw]));
fail[nnw] = fail[nw]; fail[nw] = fail[last] = nnw;
while (ch[w] == nw) ch[w] = nnw, w = fail[w];
}
}
}
inline void sign(int w, int val) {
while (w && !tag[w])
tag[w] = val, w = fail[w];
if (W == val) {
if (w <= 1) printf("-1 %d ",(int)pat[val]), W++;
else printf("%d %d ",dep[w],tag[w]-1), W += dep[w];
}
}
inline void build(char *s){
n = strlen(s+1); cnt = last = 1;
for (int i=n;i;i--) extend(i, pat[i]-'a'+1);
for (int i=1;i<=n;i++) sign(pos[i], i);
}
};
int main(){
scanf("%s",pat+1);
SAM::build(pat);
return 0;
}
看看SA将近4k的代码
再看看SAM只有1.2k的代码
SA，你还要我怎么爱你QAQ
