poj3415解题报告

这题过得实在艰难，想出了后缀数组+单调栈扫一遍的方法，但是交上去总是RE说什么也调不对，而且速度很慢，于是弃用后缀数组，启用后缀自动机。

于是，要对SAM有一些新的理解。原来只知道它能识别一个字符串中的所有z子串。如果对s1字符串构造SAM，如果用s2字符串输入自动机中，即可求出当前部分的s2中能被自动机识别的最长后缀。构造自动机后，也可求出以该后缀作结的前缀个数，设该状态为p，此个数为v，所以[tex]\begin{matrix} v_p = \sum_{q->pre = p}v_q+1\end{matrix}[/tex]，我们可以使用拓扑排序+dp，预处理出v。注意到对于一个自动机中一个状态，若与s2中tmp长的前缀相对应，则对答案的贡献为[tex]v_p*(tmp - k + 1)[/tex]。

此时则可按照par指针递归地计算出答案，具体如何实现，留作看官思考，实现时采用记忆化搜索。速度还好485MS。代码很简单。

#include<cstdio>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
#define maxn 100005
#define isl(x) (('a' <= (x) && (x) <= 'z') || ('A' <= (x) && (x) <= 'Z'))
#define get(x) (((x)<='Z')?(x-'A'):(x-'a'+26))
struct node{
    node *par, *go[52];
    long long val,f,v;
    int de;
    void clear(long long l){
        par = 0;
        memset(go,0,sizeof(go));
        val = l;
        f = -1;
        v = 1;
        de = 0;
        }
};
node pool[maxn << 2];
node *root, *last;
int tot;
long long tmp,ans,k;
char c;
void insert(int w){
    node *p = last, *np = &pool[tot++];
    np->clear(p->val+1);
    last = np;
    while(p && !p->go[w]) p->go[w] = np,p = p->par;
    if(!p){np->par = root;return;}
    node *q = p->go[w];
    if(q->val == p->val + 1){np->par = q;return;}
    node *nq = &pool[tot++];
    *nq = *q;
    nq -> val = p->val + 1;
    nq -> v = 0;
    q->par = np->par = nq;
    while(p && p->go[w] == q) p->go[w] = nq,p = p->par;
}
long long back(node *p){
    if(p->f != -1) return p->f;
    if(p->val < k) return p->f = 0;
    if(p->par->val < k) return p->f = (p->val - k + 1LL) * p->v;
        else return p->f = back(p->par) + (p->val - p->par->val) * p->v;
}
int main(){
    while(scanf("%lld",&k) == 1 && k){//change lld to I64d
        ans = tot = 0;
        root = &pool[tot++];
        root->clear(0);
        last = root;
        c = getchar();
        while(!isl(c)) c = getchar();
        while(isl(c)) {insert(get(c));c = getchar();}
        for(int i = 0;i<tot;i++) if(pool[i].par) pool[i].par->de++;
        queue<node*> Q;
        for(int i = 0;i<tot;i++) if(!pool[i].de) Q.push(&pool[i]);
        while(!Q.empty()){
            node *q = Q.front();
            Q.pop();
            if(q->par){
                q->par->de--;
                q->par->v += q->v;
                if(!q->par->de) Q.push(q->par);
                }
            }    
        tmp = 0;
        node *p = root;
        while(!isl(c)) c = getchar();
        while(isl(c)){
            if(p->go[get(c)]){
                p = p->go[get(c)];
                tmp++;
                }
                else{
                    while(p && !p->go[get(c)]) p = p -> par;
                    if(p) tmp = p->val + 1,p = p->go[get(c)];
                        else tmp = 0,p = root;
                    }
            c = getchar();      
            if(tmp < k) continue;
            if(p->par->val < k) ans += (tmp - k + 1LL) * p->v;
                else ans += back(p->par) + (tmp - p->par->val) * p->v;
            }
        printf("%lld\n",ans);//change lld to I64d
        }
    return 0;
}