hdu 4622 Reincarnation(拡張子オートモチーフ)

hdu 4622 Reincarnation（拡張子オートモチーフ）
文字列を指定します.最長2000、q個の質問をします.毎回[l,r]区間にいくつの文字列がありますか?
問題解決の考え方:前に、拡張子配列の解法http://blog.csdn.net/no__stop/articale/detail/9669325を書いたことがあります.この数日間は拡張機能を習ったので、出して書いてみました.具体的にはこうします.
まず、拡張子のモチーフの性質を知っておきたいです.自動機に文字を追加すると、val[last]-val[fa[last]個が出現したことがなく、現在の文字の末尾のサフィックスで、これほど多くの出現したことのない文字が追加されます.この性質についてはどのように来たのですか?私はparent treeの中から状態の定義とvalの代表的な意味について考えています.説明も煩雑です.知りたいのはメッセージをください.検討してみます.これはデフォルトです.みんなはこの性質を知っています.このようにしてもいいです.まずお聞きします.第一のキーワードは左エンドポイント、第二のキーワードは右エンドポイントです.このように並んでいるメリットはどこですか?query[i].l==query[i-1].l&query[i].r==query[i-1].rの問い合わせ(ここでqueryは順番に列挙します)については、前回の問い合わせではすでに[query[i-1].l,query[i-1].r]区間のansを追加しました.追加するたびにansアキュムレータval[last]-val[fa[last]を追加すればいいです.
 

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std ;



const int maxn = 11111 ;



struct sam {

    int val[maxn] , fa[maxn] , c[26][maxn] ;

    int tot , last ;



    inline int new_node ( int step ) {

        int i ;

        val[++tot] = step ;

        fa[tot] = 0 ;

        for ( i = 0 ; i < 26 ; i ++ ) c[i][tot] = 0 ;

        return tot ;

    }



    inline void extend ( int k ) {

        int i , p = last ;

        int np = new_node ( val[last] + 1 ) ;

        while ( p && !c[k][p] ) c[k][p] = np , p = fa[p] ;

        if ( !p ) fa[np] = 1 ;

        else {

            int q = c[k][p] ;

            if ( val[q] == val[p] + 1 ) fa[np] = q ;

            else {

                int nq = new_node ( val[p] + 1 ) ;

                for ( i = 0 ; i < 26 ; i ++ ) c[i][nq] = c[i][q] ;

                fa[nq] = fa[q] ;//  

                fa[q] = fa[np] = nq ;

				while ( c[k][p] == q && p ) c[k][p] = nq , p = fa[p] ;//   

            }

        }

        last = np ;

    }



    int add ( int k ) {

        extend ( k ) ;

        return val[last] - val[fa[last]] ;

    }



    int build ( char *s , int len ) {

        int i , ret = 0 ;

        tot = 0 ;

        last = new_node ( 0 ) ;

        for ( i = 0 ; i < len ; i ++ ) ret += add ( s[i] - 'a' ) ;

        return ret ;

    }



} suf ;



struct query {

    int l , r , ans ;

} q[maxn] ;

int pos[maxn] ;



bool cmp ( int i , int j ) {

    if ( q[i].l == q[j].l ) return q[i].r < q[j].r ;

    return q[i].l < q[j].l ;

}



char s[2222] , s1[2222] ;

int main () {

    int cas , m , i , j ;

    scanf ( "%d" , &cas ) ;

    while ( cas -- ) {

        scanf ( "%s" , s ) ;

        scanf ( "%d" , &m ) ;

        for ( i = 1 ; i <= m ; i ++ ) {

            pos[i] = i ;

            scanf ( "%d%d" , &q[i].l , &q[i].r ) ;

            q[i].l -- , q[i].r -- ;

        }

        sort ( pos + 1 , pos + m + 1 , cmp ) ;

        int last ;

        for ( i = 1 ; i <= m ; i ++ ) {

            int cnt = 0 ;

            if ( i == 1 ) {

                int len = 0 ;

                for ( j = q[pos[i]].l ; j <= q[pos[i]].r ; j ++ )

                    s1[len++] = s[j] ;

                s1[len] = 0 ;

                cnt = suf.build ( s1 , len ) ;

            }

            else {

                if ( q[pos[i]].l == q[pos[i-1]].l && q[pos[i]].r >= q[pos[i-1]].r ) {

                    for ( j = q[pos[i-1]].r + 1 ; j <= q[pos[i]].r ; j ++ )

                        cnt += suf.add ( s[j] - 'a' ) ;

                    cnt += last ;

                }

                else {

                    int len = 0 ;

                    for ( j = q[pos[i]].l ; j <= q[pos[i]].r ; j ++ )

                        s1[len++] = s[j] ;

                    s1[len] = 0 ;

                    cnt = suf.build ( s1 , len ) ;

                }

            }

            last = q[pos[i]].ans = cnt ;

        }

        for ( i = 1 ; i <= m ; i ++ ) printf ( "%d
" , q[i].ans ) ;

    }

}