HDU 4622 多校第三场1002 后缀自动机 (一)

比赛的时候我是用后缀数组的，但是T了。

赛后看了解题报告说，后缀数组貌似是卡你常数的时间，我算了下复杂度O(T * Q * n)。这是10 ^ 8，但是考虑到每次询问的时候都要重新构造字符，所以那个n可能是(3 - 4 ) * n，卡的可能就是这个常数。然后就过不了了。

我先上一发我的后缀数组的代码，T的好惨。

因为当时不会后缀自动机。

#include  
#include  
#include  
#include  
#include   
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)=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 '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
#include
#include
#include
#include 
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)=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 '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   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include