Hdu5801 Up Sky,Mr.Zhu (可持久化Trie+Manacher)

Hdu5801 Up Sky,Mr.Zhu

Mean

定義一個回文串的特征串為其從中心到結尾的部分，給出一個字元串\(s,q\)次詢問，每次詢問以一個字元串\(t\)為特征串字首落在區間\([L,R]\)的回文串數量，\(s\)中回文串長度不會超過\(20\)。

Sol

\(Manacher\) + 可持久\(Trie\)

和賽時想的做法差不多，但是賽時解決不了區間查詢，複雜度降不下來。

考慮到回文串的長度不超過\(20\)，那麼特征串的長度不會超過\(10\)。

對于答案而言，将回文半徑為\([1,10]\)的所有回文串分别依次處理，把貢獻累加到查詢中即可。

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define lowbit(x) (x&(-x))
#define debug(x) cout<<#x<<" :"<<x<<endl
#define debug1(x) cout<<#x<<" :"<<x<<" "
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=2e5+20;
const int M=1e5+10;
const int MAX=10000007;
inline int read() {
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
    return x*f;
}

inline void out(int x) {   
    if(x>9) out(x/10);   
    putchar(x%10+'0'); 
}     
int q[N];
char s[N];
int lens;
int m;
struct node{
    int ch[N*10][5];
    int cnt;
    int val[N*10];
    int rt[N];
    void init(){
        for(int i=0;i<=cnt;++i){
            for(int j=0;j<5;++j){
                ch[i][j]=0;
            }
            val[i]=0;
        }
        cnt = 0;
    }
    void insert(int o, int lst, char s[],int lens) {
        for (int i = 1; i <=lens ; i++) {
            int c = s[i]-'a';  
            val[o] = val[lst] + 1;  // 在原版本的基礎上更新
            if(ch[o][c]==0)ch[o][c]=++cnt;
            for(int j=0;j<5;++j){
             if(j!=c)ch[o][j]=ch[lst][j];
            }
            o=ch[o][c];
            lst=ch[lst][c];
        }
        val[o] = val[lst] + 1;
    }

  int query(int o1, int o2, char s[],int lens) {
    int ret = 0;
    for(int i=1;i<=lens;++i){
        int c = s[i]-'a';
        if(val[ch[o1][c]]-val[ch[o2][c]]){
            o1 = ch[o1][c];
            o2 = ch[o2][c];
        }
        else{
            return 0;
        }
    }
    return val[o1]-val[o2];
  }
}Trie;
char T[N*2];
int P[N*2];
int ans[N];

void manacher(const char *s,int len){
    int l=0;
    T[l++]='$';
    T[l++]='#';
    for(int i=0;i<len;++i)T[l++]=s[i],T[l++]='#';
    T[l]=0;
    int r=0,c=0;
    for(int i=0;i<l;++i){
        int &p=P[i];
        p=r>i?min(P[2*c-i],r-i):1;
        while(T[i+p]==T[i-p])p++;
        if(i+p>r)r=i+p,c=i;
    }
    
}
char kep[N];

struct as{
    int l,r;
    char s[11];
    int slen;
}ask[M];
int main(){
    while(scanf("%s",s)!=EOF){
        lens=strlen(s);
        manacher(s,lens);
        dep(i,lens,1){
            s[i]=s[i-1];
        }
        scanf("%d",&m);
        rep(i,1,m){
            ask[i].l=read();
            ask[i].r=read();
            scanf("%s",ask[i].s+1);
            ask[i].slen = strlen(ask[i].s+1);
        }

        for(int i=1;i<=10;++i){
            Trie.init();
            Trie.rt[0]=++Trie.cnt;
            for(int j=1;j<=lens;j++){//even
                int r = (P[j*2-1])/2;
                if(r>=i){
                    Trie.rt[j]=++Trie.cnt;
                    int con=0;
                    rep(h,j,j+r-1)kep[++con]=s[h];
                    kep[con+1]='\0';
                    Trie.insert(Trie.rt[j],Trie.rt[j-1],kep,con);                
                }
                else Trie.rt[j]=Trie.rt[j-1];
            }                
            for(int j=1;j<=m;++j){//even
                if(ask[j].slen>i||ask[j].r-ask[j].l+1<i*2)continue;
                ans[j] += Trie.query(Trie.rt[ask[j].r-i+1],Trie.rt[ask[j].l+i-1],ask[j].s,ask[j].slen);
            }

            Trie.init();
            Trie.rt[0]=++Trie.cnt;
            for(int j=1;j<=lens;++j){//odd
                int r = (P[j*2])/2;
                if(r>=i){
                    Trie.rt[j]=++Trie.cnt;
                    int con=0;
                    rep(h,j,j+r-1)kep[++con]=s[h];
                    kep[con+1]='\0';
                    Trie.insert(Trie.rt[j],Trie.rt[j-1],kep,con);                
                }
                else Trie.rt[j]=Trie.rt[j-1];    
            }
           
            for(int j=1;j<=m;++j){//odd
                if(ask[j].slen>i||ask[j].r-ask[j].l+1<i*2-1)continue;
                ans[j] += Trie.query(Trie.rt[ask[j].r-i+1],Trie.rt[ask[j].l+i-2],ask[j].s,ask[j].slen);
            }
        }

        rep(i,1,m){
            printf("%d\n",ans[i]);
            ans[i]=0;
        }
    }
    return 0;
}             
/*
bceaeedde
5
5 8 e
3 5 e
1 2 a
5 9 d
5 9 de

3
2
0
4
1
 */