struct state {
int len,link;
int nxt[31];
};
char s[N];
int n,ans,t[N],a[N],b[N],O;
struct SAM {
state st[N*2];
int siz,last;
void init() {
for(int i=0; i<=O; i++) {
st[i].len=0;
st[i].link=0;
for(int j=0; j<31; j++) {
st[i].nxt[j]=-1;
}
}
siz=1;
last=1;
}
void extend(int c) {
int cur=++siz,p=last;
st[cur].len=st[last].len+1;
b[cur]=1;
while(p!=0&&st[p].nxt[c]<0) {
st[p].nxt[c]=cur;
p=st[p].link;
}
if(p==0) st[cur].link=1;
else {
int q=st[p].nxt[c];
if(st[p].len+1==st[q].len) {
st[cur].link=q;
} else {
int k=++siz;
st[k].len=st[p].len+1;
memcpy(st[k].nxt,st[q].nxt,sizeof st[k].nxt);
st[k].link=st[q].link;
while(p!=0&&st[p].nxt[c]==q) {
st[p].nxt[c]=k;
p=st[p].link;
}
st[q].link=st[cur].link=k;
}
}
last=cur;
}
} Sam;
int sum[N],k,T;
void solve() {
ans=n+1;
for(int i=1; i<=Sam.siz; i++) t[Sam.st[i].len]++;
for(int i=1; i<=Sam.siz; i++) t[i]+=t[i-1];
for(int i=1; i<=Sam.siz; i++) a[t[Sam.st[i].len]--]=i;
for(int i=Sam.siz; i; i--) {
int x=a[i];
b[Sam.st[x].link]+=b[x];
}
}
原文链接: https://www.cnblogs.com/Diamondan/p/17072152.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/314633
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!