SPOJ NSUBSTR 접미사 자동 동기 + DP

제목
길이 가 S 인 문자열 을 주 고 길이 가 1 - S 인 하위 문자열 이 최대 몇 번 나 왔 는 지 물 어보 세 요.
해제
DP 는 사실 매우 간단 하 다.주로 접미사 자동 동기 템 플 릿 입 니 다. 잘 두 드 리 면 됩 니 다.알고리즘 에 대해 접미사 자동 기 를 진지 하 게 관찰 하고 접미사 자동 기 를 철저히 이해 하면 이것 이 템 플 릿 문제 라 는 것 을 알 수 있다.이 문제 에 대해 제 가 발견 한 규칙 은 한 점 에 대해 우 리 는 발생 횟수 를 쉽게 계산 한 다음 에 이 점 에 대응 하 는 문자열 의 최 장 길이 가 얼마 인지 볼 수 있 습 니 다. 그러면 이 길이 보다 작은 모든 문자열 의 출현 횟수 는 이 점 의 출현 횟수 (RT 배열) 입 니 다.
코드

#include 
#define UP(i,l,h) for(int i=l;i
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(t) while(t)
#define MEM(a,b) memset(a,b,sizeof(a))
#define MAXN 350010
using namespace std;
static const int NODE=MAXN<<1,C=26;
char s[MAXN];
int dp[MAXN];
struct SuffixAuto {
    int allc,n,last,par[NODE],len[NODE],tran[NODE][C],c[NODE],id[NODE],rt[NODE];
    int newNode() {
        int now=++allc;
        MEM(tran[now],0);
        return now;
    }
    void init() {
        MEM(c,0);
        MEM(id,0);
        MEM(rt,0);
        allc=0;
        last=newNode();
        par[last]=len[last]=0;
    }
    void extend(int c) {
        int p=last,np=newNode();
        len[np]=len[last]+1;
        rt[np]=1;
        for(; p&&!tran[p][c]; p=par[p]) tran[p][c]=np;
        if(!p) par[np]=1;
        else {
            int q=tran[p][c];
            if(len[q]==len[p]+1) par[np]=q;
            else {
                int nq=++allc;
                par[nq]=par[q];
                len[nq]=len[p]+1;
                memcpy(tran[nq],tran[q],sizeof(tran[q]));
                par[np]=par[q]=nq;
                for(tran[p][c]=nq,p=par[p]; p&&tran[p][c]==q; p=par[p]) tran[p][c]=nq;
            }
        }
        last=np;
    }
    void topsort() {
        UP(i,1,allc+1) c[len[i]]++;
        UP(i,1,n+1) c[i]+=c[i-1];
        UP(i,1,allc+1) id[c[len[i]]--]=i;
        DOWN(i,allc+1,1) rt[par[id[i]]]+=rt[id[i]];
    }
};
SuffixAuto sa;

int main() {
    W(~scanf("%s",s)) {
        MEM(dp,0);
        sa.init();
        int len=strlen(s);
        sa.n=len;
        UP(i,0,len) {
            sa.extend(s[i]-'a');
        }
        sa.topsort();
        UP(i,1,sa.allc+1) {
            int x=sa.id[i];
            dp[sa.len[x]]=max(dp[sa.len[x]],sa.rt[x]);
//            cout<
        }
        DOWN(i,len,1) dp[i]=max(dp[i+1],dp[i]);
        UP(i,1,len+1) printf("%d
",dp[i]);
    }
}