hdu 4622 Reincarnation (접미사 자동 동기, 입문 급)

제목: 문자열 의 임의의 문자열 의 다른 문자열 수 를 구하 십시오.사고: 접미사 자동 동기 로 O (n2) 의 예비 처 리 를 할 수 있 고 O (1) 는 조회 에 대답 할 수 있 습 니 다.근 데 제 코드 가 1000 + ms 를 뛰 었 습 니 다. 다른 사람의 코드 는 100 ms - 200 ms 까지 달 릴 수 있 습 니 다.VJ 의 기록

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define rep(i, s, t) for(int (i)=(s);(i)<=(t);++(i))
const int N = 2005;
typedef long long LL;

struct State {
    State *link, *go[26];
    int len;
    void clear() {
        link = 0; len = 0; memset(go, 0, sizeof(go));
    }
    int calc() {
        if ( link == 0 ) return 0;
        return len - link->len;
    }
} *root, *last, *cur;

const int MaxLength = N;
State statePool[MaxLength*2];

void init() {
    cur = statePool;
    root = last = cur ++;
    root->clear();
}

int tot = 0;

void sa_insert(int ch) {
    //cout << "Insert " << (char)ch << endl;
    ch -= 'a';
    State *p = last;
    State *np = cur ++;
    np->clear();
    np->len = p->len + 1;
    while ( p && !p->go[ch] ) {
        p->go[ch] = np; p = p->link;
    }
    if ( p == 0 ) {
        np->link = root;
    } else {
        State *q = p->go[ch];
        if ( p->len + 1 == q->len ) {
            np->link = q;
        } else {
            State *nq = cur ++;
            nq->clear();
            memcpy(nq->go, q->go, sizeof(q->go));

            tot -= q->calc();

            nq->len = p->len + 1;
            nq->link = q->link;
            q->link = nq;
            np->link = nq;

            tot += q->calc() + nq->calc();

            while( p && p->go[ch] == q ) {
                p->go[ch] = nq; p = p->link;
            }
        }
    }
    tot += np->calc();
    last = np;
}

int cnt[N][N], n;
char buf[N];

int main() {
#ifdef _LOCA_ENV_
    freopen("input.in", "r", stdin);
#endif // _LOCA_ENV
    int t;
    scanf("%d", &t);
    while ( t -- ) {
        scanf("%s", buf);
        //cout << buf << endl;
        scanf("%d", &n);
        int len = strlen(buf);
        rep(i, 0, len-1) {
            init();
            tot = 0;
            rep(j, i, len-1) {
                sa_insert(buf[j]);
                cnt[i][j] = tot;
            }
        }
        rep(i, 1, n) {
            int l, r;
            scanf("%d%d", &l, &r);
            -- l, -- r;
            printf("%d
", cnt[l][r]);
        }
    }
    return 0;
}