HDU 4622 多校第三場1002 後綴自動機

比賽的時候我是用後綴數組的，但是T了。

賽後看了解題報告說，後綴數組貌似是卡你常數的時間，我算了下復雜度O(T * Q * n)。這是10 ^ 8，但是考慮到每次詢問的時候都要重新構造字符，所以那個n可能是(3 - 4 ) * n，卡的可能就是這個常數。然後就過不了了。

我先上一發我的後綴數組的代碼，T的好慘。

因為當時不會後綴自動機。

#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include <cstdio>  
using namespace std; 
const int N=2005; 
/****後綴數組模版****/ 
#define F(x)((x)/3+((x)%3==1?0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置  
#define G(x)((x)<tb?(x)*3+1:((x)-tb)*3+2) //G(x)是計算新字符串的suffix(x)在原字符串中的位置，和F(x)為互逆運算  
int wa[N],wb[N],wv[N],WS[N]; 
int sa[N*3] ; 
int rank1[N],height[N]; 
int r[N*3]; 
 
int c0(int *r,int a,int b) { 
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2]; 
} 
int c12(int k,int *r,int a,int b) { 
    if(k==2) 
        return r[a]<r[b] || ( r[a]==r[b] && c12(1,r,a+1,b+1) ); 
    else 
        return r[a]<r[b] || ( r[a]==r[b] && wv[a+1]<wv[b+1] ); 
} 
void sort(int *r,int *a,int *b,int n,int m) { 
    int i; 
    for(i=0; i<n; i++) 
        wv[i]=r[a[i]]; 
    for(i=0; i<m; i++) 
        WS[i]=0; 
    for(i=0; i<n; i++) 
        WS[wv[i]]++; 
    for(i=1; i<m; i++) 
        WS[i]+=WS[i-1]; 
    for(i=n-1; i>=0; i--) 
        b[--WS[wv[i]]]=a[i]; 
    return; 
} 
 
//注意點：為了方便下面的遞歸處理，r數組和sa數組的大小都要是3*n  
void dc3(int *r,int *sa,int n,int m) { //rn數組保存的是遞歸處理的新字符串，san數組是新字符串的sa  
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = (n+1)/3 , tbc = 0 , p; 
    r[n] = r[n+1] = 0; 
    for(i=0; i<n; i++) { 
        if(i%3!=0) 
            wa[tbc++]=i; //tbc表示起始位置模3為1或2的後綴個數  
    } 
    sort(r+2,wa,wb,tbc,m); 
    sort(r+1,wb,wa,tbc,m); 
    sort(r,wa,wb,tbc,m); 
    for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++) 
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++; 
    if(p<tbc) 
        dc3(rn,san,tbc,p); 
    else { 
        for(i=0; i<tbc; i++) 
            san[rn[i]]=i; 
    } 
//對所有起始位置模3等於0的後綴排序  
    for(i=0; i<tbc; i++) { 
        if(san[i]<tb) 
            wb[ta++]=san[i]*3; 
    } 
    if(n%3==1)  //n%3==1，要特殊處理suffix(n-1)  
        wb[ta++]=n-1; 
    sort(r,wb,wa,ta,m); 
    for(i=0; i<tbc; i++) 
        wv[wb[i]=G(san[i])]=i; 
//合並所有後綴的排序結果，保存在sa數組中  
    for(i=0,j=0,p=0; i<ta&&j<tbc; p++) 
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++]; 
    for(; i<ta; p++) 
        sa[p]=wa[i++]; 
    for(; j<tbc; p++) 
        sa[p]=wb[j++]; 
    return; 
} 
 
//height[i]=suffix(sa[i-1])和suffix(sa[i])的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴  
void calheight(int *r,int *sa,int n) { 
    int i,j,k=0; 
    for(i=1; i<=n; i++) 
        rank1[sa[i]]=i; 
    for(i=0; i<n; height[rank1[i++]]=k) 
        for(k?k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++); 
} 
int solve(int n) { 
    int i,sum=0; 
    for(i=1; i<=n; i++) { 
        sum += n - sa[i] - height[i] ; 
    } 
 
    return sum; 
} 
/****以上模版****/ 
char now[2005] ; 
char str[N]; 
inline void RD(int &ret) { 
    char c; 
    do { 
        c = getchar(); 
    } while(c < '0' || c > '9') ; 
    ret = c - '0'; 
    while((c=getchar()) >= '0' && c <= '9') 
        ret = ret * 10 + ( c - '0' ); 
} 
inline void OT(int a) { 
    if(a >= 10)OT(a / 10) ; 
    putchar(a % 10 + '0') ; 
} 
struct QU { 
    int s ,e ,id ; 
} QQ[10005] ; 
bool cmp(QU a ,QU b) { 
    if(a.s == b.s)return a.e < b.e ; 
    return a.s < b.s ; 
} 
int ans[11111] ; 
int main() { 
    int i,n,t; 
    scanf("%d",&t); 
    while(t--) { 
        scanf("%s",str); 
        memset(ans , 0 , sizeof(ans)); 
        int xd ; 
        cin >> xd ; 
        for (int i = 0 ; i < xd ; i ++ ) { 
            RD(QQ[i].s) ; 
            RD(QQ[i].e) ; 
            QQ[i].s -- ; 
            QQ[i].e -- ; 
            QQ[i].id = i ; 
        } 
        sort(QQ , QQ + xd , cmp) ; 
        int st = QQ[0].s ; 
        int ed = QQ[0].e ; 
        int num = 0 ; 
        for (int i = st ; i <= ed ; i ++ )r[num ++] = (int)str[i] ; 
        r[num] = 0 ; 
        dc3(r , sa ,num + 1 , 200) ; 
        calheight(r , sa, num ) ; 
        ans[QQ[0].id] = solve(num) ; 
        for (int i = 1 ; i < xd ; i ++ ) { 
            if(QQ[i].s != QQ[i - 1].s) { 
                num = 0 ; 
                for (int j = QQ[i].s ; j <= QQ[i].e ; j ++ )r[num ++] = (int)str[j] ; 
                r[num] = 0 ; 
                dc3(r , sa , num + 1 ,200 ) ; 
                calheight(r ,sa ,num) ; 
                ans[QQ[i].id] = solve(num) ; 
                ed = QQ[i].e ; 
            } else { 
                if(QQ[i].e == QQ[i - 1].e) { 
                    ans[QQ[i].id] = ans[QQ[i - 1].id] ; 
                } else { 
                    for (int j = ed + 1 ; j <= QQ[i].e ; j ++)r[num ++] = (int)str[j] ; 
                    r[num] = 0 ; 
                    dc3(r ,sa ,num + 1 , 200) ; 
                    calheight(r ,sa ,num) ; 
                    ans[QQ[i].id] = solve(num) ; 
                    ed = QQ[i].e ; 
                } 
            } 
        } 
        for (int i = 0 ; i < xd ; i ++ ) { 
            OT(ans[i]) ; 
            puts("") ; 
        } 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include <cstdio>
using namespace std;
const int N=2005;
/****後綴數組模版****/
#define F(x)((x)/3+((x)%3==1?0:tb)) //F(x)求出原字符串的suffix(x)在新的字符串中的起始位置
#define G(x)((x)<tb?(x)*3+1:((x)-tb)*3+2) //G(x)是計算新字符串的suffix(x)在原字符串中的位置，和F(x)為互逆運算
int wa[N],wb[N],wv[N],WS[N];
int sa[N*3] ;
int rank1[N],height[N];
int r[N*3];

int c0(int *r,int a,int b) {
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b) {
    if(k==2)
        return r[a]<r[b] || ( r[a]==r[b] && c12(1,r,a+1,b+1) );
    else
        return r[a]<r[b] || ( r[a]==r[b] && wv[a+1]<wv[b+1] );
}
void sort(int *r,int *a,int *b,int n,int m) {
    int i;
    for(i=0; i<n; i++)
        wv[i]=r[a[i]];
    for(i=0; i<m; i++)
        WS[i]=0;
    for(i=0; i<n; i++)
        WS[wv[i]]++;
    for(i=1; i<m; i++)
        WS[i]+=WS[i-1];
    for(i=n-1; i>=0; i--)
        b[--WS[wv[i]]]=a[i];
    return;
}

//注意點：為了方便下面的遞歸處理，r數組和sa數組的大小都要是3*n
void dc3(int *r,int *sa,int n,int m) { //rn數組保存的是遞歸處理的新字符串，san數組是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = (n+1)/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for(i=0; i<n; i++) {
        if(i%3!=0)
            wa[tbc++]=i; //tbc表示起始位置模3為1或2的後綴個數
    }
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1; i<tbc; i++)
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    if(p<tbc)
        dc3(rn,san,tbc,p);
    else {
        for(i=0; i<tbc; i++)
            san[rn[i]]=i;
    }
//對所有起始位置模3等於0的後綴排序
    for(i=0; i<tbc; i++) {
        if(san[i]<tb)
            wb[ta++]=san[i]*3;
    }
    if(n%3==1)  //n%3==1，要特殊處理suffix(n-1)
        wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0; i<tbc; i++)
        wv[wb[i]=G(san[i])]=i;
//合並所有後綴的排序結果，保存在sa數組中
    for(i=0,j=0,p=0; i<ta&&j<tbc; p++)
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    for(; i<ta; p++)
        sa[p]=wa[i++];
    for(; j<tbc; p++)
        sa[p]=wb[j++];
    return;
}

//height[i]=suffix(sa[i-1])和suffix(sa[i])的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴
void calheight(int *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1; i<=n; i++)
        rank1[sa[i]]=i;
    for(i=0; i<n; height[rank1[i++]]=k)
        for(k?k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++);
}
int solve(int n) {
    int i,sum=0;
    for(i=1; i<=n; i++) {
        sum += n - sa[i] - height[i] ;
    }

    return sum;
}
/****以上模版****/
char now[2005] ;
char str[N];
inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
inline void OT(int a) {
    if(a >= 10)OT(a / 10) ;
    putchar(a % 10 + '0') ;
}
struct QU {
    int s ,e ,id ;
} QQ[10005] ;
bool cmp(QU a ,QU b) {
    if(a.s == b.s)return a.e < b.e ;
    return a.s < b.s ;
}
int ans[11111] ;
int main() {
    int i,n,t;
    scanf("%d",&t);
    while(t--) {
        scanf("%s",str);
        memset(ans , 0 , sizeof(ans));
        int xd ;
        cin >> xd ;
        for (int i = 0 ; i < xd ; i ++ ) {
            RD(QQ[i].s) ;
            RD(QQ[i].e) ;
            QQ[i].s -- ;
            QQ[i].e -- ;
            QQ[i].id = i ;
        }
        sort(QQ , QQ + xd , cmp) ;
        int st = QQ[0].s ;
        int ed = QQ[0].e ;
        int num = 0 ;
        for (int i = st ; i <= ed ; i ++ )r[num ++] = (int)str[i] ;
        r[num] = 0 ;
        dc3(r , sa ,num + 1 , 200) ;
        calheight(r , sa, num ) ;
        ans[QQ[0].id] = solve(num) ;
        for (int i = 1 ; i < xd ; i ++ ) {
            if(QQ[i].s != QQ[i - 1].s) {
                num = 0 ;
                for (int j = QQ[i].s ; j <= QQ[i].e ; j ++ )r[num ++] = (int)str[j] ;
                r[num] = 0 ;
                dc3(r , sa , num + 1 ,200 ) ;
                calheight(r ,sa ,num) ;
                ans[QQ[i].id] = solve(num) ;
                ed = QQ[i].e ;
            } else {
                if(QQ[i].e == QQ[i - 1].e) {
                    ans[QQ[i].id] = ans[QQ[i - 1].id] ;
                } else {
                    for (int j = ed + 1 ; j <= QQ[i].e ; j ++)r[num ++] = (int)str[j] ;
                    r[num] = 0 ;
                    dc3(r ,sa ,num + 1 , 200) ;
                    calheight(r ,sa ,num) ;
                    ans[QQ[i].id] = solve(num) ;
                    ed = QQ[i].e ;
                }
            }
        }
        for (int i = 0 ; i < xd ; i ++ ) {
            OT(ans[i]) ;
            puts("") ;
        }
    }
    return 0;
}

昨天晚上和今天一直在看後綴自動機，這裡推薦一個我看的懂的博客。

http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html


算是學會了使用模版。當然也僅限於模版題。。好水。。繼續學習。。


[cpp] view plaincopyprint?
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 2505  
#define inf 1<<28  
#define LL(x) ( x << 1 )  
#define RR(x) ( x << 1 | 1 )  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
inline void RD(int &ret) { 
    char c; 
    do { 
        c = getchar(); 
    } while(c < '0' || c > '9') ; 
    ret = c - '0'; 
    while((c=getchar()) >= '0' && c <= '9') 
        ret = ret * 10 + ( c - '0' ); 
} 
inline void OT(int a){ 
    if(a >= 10)OT(a / 10) ; 
    putchar(a % 10 + '0') ; 
} 
struct SAM { 
    SAM*pre ,*next[26] ; 
    int val ; 
    void clear() { 
        pre = 0 ; 
        val = 0 ; 
        mem(next ,0) ; 
    } 
} ; 
SAM *root ,*last  ,*cur ; 
SAM qe[111111] ; 
int cnt = 0 ; 
void init() { 
    cnt = 0 ; 
    root = last = &qe[cnt ++] ; 
    root -> clear() ; 
} 
struct QU{ 
    int s ,e ,id ; 
}QQ[100005] ; 
void extend(int w ) { 
    SAM*p = last ; 
    SAM*np = &qe[cnt ++] ; 
    np -> clear() ; 
    np -> val = p -> val + 1 ; 
    while(p && !p -> next[w] )p -> next[w] = np ,p = p -> pre ; 
    if(!p) { 
        np -> pre = root ; 
    } else { 
        SAM *q = p -> next[w] ; 
        if(p -> val + 1 == q -> val) { 
            np -> pre = q ; 
        } else { 
            SAM *nq =  &qe[cnt ++] ; 
            nq -> clear() ; 
            memcpy(nq -> next ,q -> next ,sizeof(q -> next)) ; 
 
            nq -> val = p -> val + 1 ; 
            nq -> pre = q -> pre ; 
            q -> pre = nq ; 
            np -> pre = nq ; 
            while(p && p -> next[w] == q) { 
                p -> next[w] = nq ; 
                p = p -> pre ; 
            } 
        } 
    } 
    last = np ; 
} 
 
#define N 100005  
#define M 2005  
char a[M] ; 
bool cmp(QU a ,QU b){ 
    if(a.s == b.s)return a.e < b.e ; 
    return a.s < b.s ; 
} 
int solve(){ 
    int sum = 0 ; 
    for (int i = cnt - 1 ; i > 0 ; i -- ){ 
        sum += qe[i].val - qe[i].pre -> val ; 
    } 
    return sum ; 
} 
int ans[N] ; 
int main() { 
    int T ; 
    cin >> T ; 
    while( T -- ) { 
        cin >> a ; 
        mem(ans, 0) ; 
        int l = strlen(a) ; 
        int Q ; 
        cin >> Q ; 
        for (int i = 0 ; i < Q ; i ++ ){ 
            RD(QQ[i].s) ; 
            RD(QQ[i].e) ; 
            QQ[i].s -- ; 
            QQ[i].e -- ; 
            QQ[i].id = i ; 
        } 
        sort(QQ , QQ + Q , cmp) ; 
        init() ; 
        int st = QQ[0].s ; 
        int ed = QQ[0].e ; 
        for (int i = st ; i <= ed ; i ++ ){ 
            extend(a[i] - 'a') ; 
        } 
        for (int i = cnt - 1 ; i > 0 ; i -- ){ 
            ans[QQ[0].id] += qe[i].val - qe[i].pre -> val ; 
        } 
        for (int i = 1 ; i < Q ;i ++ ){ 
//            cout << QQ[i].s << " " << QQ[i].e << endl;  
//            getchar() ;  
            if(QQ[i].s != QQ[i - 1].s){ 
                init() ; 
                for (int j = QQ[i].s ; j <= QQ[i].e ; j ++ )extend(a[j] - 'a' ) ; 
                ans[QQ[i].id] = solve() ; 
            } 
            else { 
                if(QQ[i].e == QQ[i - 1].e){ 
                    ans[QQ[i].id] = ans[QQ[i - 1].id] ; 
                }else{ 
                    for (int j = ed + 1 ; j <= QQ[i].e ; j ++ )extend(a[j] - 'a' ) ; 
                    ans[QQ[i].id] = solve() ; 
                } 
            } 
            ed = QQ[i].e ; 
        } 
        for (int i = 0 ; i < Q ;i ++ ){ 
            OT(ans[i]) ; 
            puts("") ; 
        } 
    } 
    return 0 ; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;

inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
    if(a >= 10)OT(a / 10) ;
    putchar(a % 10 + '0') ;
}
struct SAM {
    SAM*pre ,*next[26] ;
    int val ;
    void clear() {
        pre = 0 ;
        val = 0 ;
        mem(next ,0) ;
    }
} ;
SAM *root ,*last  ,*cur ;
SAM qe[111111] ;
int cnt = 0 ;
void init() {
    cnt = 0 ;
    root = last = &qe[cnt ++] ;
    root -> clear() ;
}
struct QU{
    int s ,e ,id ;
}QQ[100005] ;
void extend(int w ) {
    SAM*p = last ;
    SAM*np = &qe[cnt ++] ;
    np -> clear() ;
    np -> val = p -> val + 1 ;
    while(p && !p -> next[w] )p -> next[w] = np ,p = p -> pre ;
    if(!p) {
        np -> pre = root ;
    } else {
        SAM *q = p -> next[w] ;
        if(p -> val + 1 == q -> val) {
            np -> pre = q ;
        } else {
            SAM *nq =  &qe[cnt ++] ;
            nq -> clear() ;
            memcpy(nq -> next ,q -> next ,sizeof(q -> next)) ;

            nq -> val = p -> val + 1 ;
            nq -> pre = q -> pre ;
            q -> pre = nq ;
            np -> pre = nq ;
            while(p && p -> next[w] == q) {
                p -> next[w] = nq ;
                p = p -> pre ;
            }
        }
    }
    last = np ;
}

#define N 100005
#define M 2005
char a[M] ;
bool cmp(QU a ,QU b){
    if(a.s == b.s)return a.e < b.e ;
    return a.s < b.s ;
}
int solve(){
    int sum = 0 ;
    for (int i = cnt - 1 ; i > 0 ; i -- ){
        sum += qe[i].val - qe[i].pre -> val ;
    }
    return sum ;
}
int ans[N] ;
int main() {
    int T ;
    cin >> T ;
    while( T -- ) {
        cin >> a ;
        mem(ans, 0) ;
        int l = strlen(a) ;
        int Q ;
        cin >> Q ;
        for (int i = 0 ; i < Q ; i ++ ){
            RD(QQ[i].s) ;
            RD(QQ[i].e) ;
            QQ[i].s -- ;
            QQ[i].e -- ;
            QQ[i].id = i ;
        }
        sort(QQ , QQ + Q , cmp) ;
        init() ;
        int st = QQ[0].s ;
        int ed = QQ[0].e ;
        for (int i = st ; i <= ed ; i ++ ){
            extend(a[i] - 'a') ;
        }
        for (int i = cnt - 1 ; i > 0 ; i -- ){
            ans[QQ[0].id] += qe[i].val - qe[i].pre -> val ;
        }
        for (int i = 1 ; i < Q ;i ++ ){
//            cout << QQ[i].s << " " << QQ[i].e << endl;
//            getchar() ;
            if(QQ[i].s != QQ[i - 1].s){
                init() ;
                for (int j = QQ[i].s ; j <= QQ[i].e ; j ++ )extend(a[j] - 'a' ) ;
                ans[QQ[i].id] = solve() ;
            }
            else {
                if(QQ[i].e == QQ[i - 1].e){
                    ans[QQ[i].id] = ans[QQ[i - 1].id] ;
                }else{
                    for (int j = ed + 1 ; j <= QQ[i].e ; j ++ )extend(a[j] - 'a' ) ;
                    ans[QQ[i].id] = solve() ;
                }
            }
            ed = QQ[i].e ;
        }
        for (int i = 0 ; i < Q ;i ++ ){
            OT(ans[i]) ;
            puts("") ;
        }
    }
    return 0 ;
}