JZOJ 3572 基因模式

首先对 T 建 SAM，对 1≤i≤|S|，求出 li=max{j∣Si…j∈substrings(T)}。

设 pi=i−li+1，显然 pi 是单调不降的，考虑用一些整体标记来维护答案。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5;
const int S = 1 << 4;
int n,m,q;
char s[N + 5],t[N + 5],id[128],res[4];
namespace SAM
{
    struct node
    {
        int ch[4];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
}
int l,cnt[S + 5],cur,tag;
long long ans;
int main()
{
    id['C'] = id['c'] = 1,id['G'] = id['g'] = 2,id['T'] = id['t'] = 3;
    scanf("%d%s",&q,s + 1),n = strlen(s + 1);
    for(register int i = 1;i <= n;++i)
        SAM::insert(id[s[i]]);
    for(;q;--q)
    {
        l = 1,cur = tag = ans = 0,memset(cnt,0,sizeof cnt);
        scanf("%s%s",s + 1,t),m = strlen(s + 1),memset(res,-1,sizeof res);
        for(register char *c = t;*c;res[id[*c]] = *c >= 'A' && *c <= 'Z',++c);
        for(register int i = 1,x,p = 1,len = 0;i <= m;++i)
        {
            x = id[s[i]];
            if(SAM::sam[p].ch[x])    
                p = SAM::sam[p].ch[x],++len;
            else
            {
                for(;p && !SAM::sam[p].ch[x];p = SAM::sam[p].fa);
                !p ? (p = 1,len = 0) : (len = SAM::sam[p].len + 1,p = SAM::sam[p].ch[x]);
            }
            for(;l < i - len + 1;++l)
                --cnt[cur ^ tag],cur ^= 1 << id[s[l]];
            tag ^= 1 << x,cur ^= 1 << x,++cnt[tag ^ (1 << x)];
            for(register int i0 = 0;i0 < 2;++i0)
                if(res[0] == -1 || res[0] == i0)
                    for(register int i1 = 0;i1 < 2;++i1)
                        if(res[1] == -1 || res[1] == i1)
                            for(register int i2 = 0;i2 < 2;++i2)
                                if(res[2] == -1 || res[2] == i2)
                                    for(register int i3 = 0;i3 < 2;++i3)
                                        if(res[3] == -1 || res[3] == i3)
                                            ans += cnt[(i0 | (i1 << 1) | (i2 << 2) | (i3 << 3)) ^ tag];
        }
        printf("%lld\n",ans);
    }
}