题目链接：http://poj.org/problem?id=3729

题意：给出两个数字串A和B以及K。求A有多少个长度为K的子串同时是B的子串且这个子串加上在A中后面一个数字时不是B的子串？

思路：统计大于等于K的减去大于等于K+1的。

int r[N],sa[N],wa[N],wb[N],wd[N],rank[N],h[N];int cmp(int *r,int a,int b,int len){    return r[a]==r[b]&&r[a+len]==r[b+len];}void da(int *r,int *sa,int n,int m){    int i,j,p,*x=wa,*y=wb,*t;    FOR0(i,m) wd[i]=0;    FOR0(i,n) wd[x[i]=r[i]]++;    FOR1(i,m-1) wd[i]+=wd[i-1];    FORL0(i,n-1) sa[--wd[x[i]]]=i;    for(j=1,p=1;p
     
      <<=1,m=p)    {        p=0;        FOR(i,n-j,n-1) y[p++]=i;        FOR0(i,n) if(sa[i]>=j) y[p++]=sa[i]-j;        FOR0(i,m) wd[i]=0;        FOR0(i,n) wd[x[i]]++;        FOR1(i,m-1) wd[i]+=wd[i-1];        FORL0(i,n-1) sa[--wd[x[y[i]]]]=y[i];        t=x;x=y;y=t;p=1;x[sa[0]]=0;        FOR1(i,n-1) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;    }}void calHeight(int *r,int *sa,int n){    int i,j,k=0;    FOR1(i,n) rank[sa[i]]=i;    FOR0(i,n)    {        if(k) k--;        j=sa[rank[i]-1];        while(i+k
      
       
        M) break;        R=L;        while(R<=M&&h[R]>=x) R++;        k=t=0;        FOR(j,L-1,R-1)        {            if(sa[j]
        
         n) t=1;        }        ans+=(i64)k*t;        i=R;    }    return ans;}int main(){    while(scanf("%d%d%d",&n,&m,&K)!=-1)    {        int i,j,L=0;        FOR0(i,n) RD(r[L]),r[L]++,L++;        r[L++]=10002;        FOR0(i,m) RD(r[L]),r[L]++,L++;        r[L]=0;        da(r,sa,L+1,10003);        calHeight(r,sa,L);        M=L;        i64 ans=cal(K)-cal(K+1);        PR(ans);    }    return 0;}