欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

牛客19822 我不爱她

程序员文章站 2022-04-09 10:53:21
AC自动机...

链接

点击跳转

题解

把所有的串丢进AC自动机

AC自动机上的每个节点都有一个权值,这个权值代表“如果一个串匹配到这里,会对答案造成多大的贡献”

这个东西怎么算呢?

如果直接对fail链上的(深度×\times经过这个点的串个数)求和,这样是会算重复的

比如aaaaaaaa这个串扔进AC自动机,如果我拿baaaabaaaa来跑一下,匹配上的是前缀aaaaaaaa,那么因为对fail链上求和,所以直接求出的贡献是4+3+2+14+3+2+1,显然算多了很多,算多了3+2+13+2+1,我只需要4就可以

那么我就差分,我对fail链上的((深度-next[深度])×\times经过这个点的串个数)求和,就对了,这样相当于每次只增加一个增量

代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1500010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-0x30;
    return f*x;
}
struct KMP
{
    int n, next[maxn], t[maxn];
    void build(int *r, int len)
    {
        int i, j=0;
        n=len;
        for(i=1;i<=len;i++)t[i]=r[i];  t[len+1]=0;
        for(i=2;i<=len;i++)
        {
            for(;j and t[j+1]!=t[i];j=next[j]);
            next[i] = t[j+1]==t[i]?++j:0;
        }
    }
    int move(int pos, int x)
    {
        for(;pos and t[pos+1]!=x;pos=next[pos]);
        return t[pos+1]==x ? pos+1 : 0;
    }
}kmp;
struct ACautomaton
{
    int trie[maxn][30], tot, fail[maxn], tail[maxn];
    ll w[maxn];
    void clear()     //clear the arrays
    {
        for(int i=1;i<=tot;i++)cl(trie[i]), fail[i]=w[i]=tail[i]=0;
        tot=1;
    }
    int insert(int *r, int len)     //insert a string into trie tree
    {
        kmp.build(r,len);
        auto pos=1;
        for(auto i=1;i<=len;i++)
        {
            pos = trie[pos][r[i]] ? trie[pos][r[i]] : trie[pos][r[i]]=++tot;
            w[pos] += i-kmp.next[i];
        }
        tail[pos]++;
        return pos;
    }
    void build()    //build the aca
    {
        queue<int> q;
        int u, v, f;
        q.push(1);
        while(!q.empty())
        {
            u=q.front(); q.pop();
            for(auto i=1;i<=26;i++)
                if(trie[u][i])
                {
                    v=trie[u][i];
                    for(f=fail[u];f and !trie[f][i];f=fail[f]);
                    fail[v] = f ? trie[f][i] : 1;
                    tail[v]+=tail[fail[v]];
                    w[v]+=w[fail[v]];
                    q.push(v);
                }
        }
    }
    int move(int pos, int c)
    {
        for(;pos and !trie[pos][c];pos=fail[pos]);
        return pos ? trie[pos][c] : 1;
    }
}aca;
int pos[maxn], len[maxn], r[maxn];
char s[maxn];
int main()
{
    ll T=read();
    while(T--)
    {
        ll ans=0, n=read(), i, j;
        aca.clear();
        len[0]=1;
        rep(i,1,n)
        {
            pos[i] = pos[i-1] + len[i-1];
            scanf("%s",s+pos[i]);
            len[i] = strlen(s+pos[i]);
        }
        rep(i,1,pos[n]+len[n]-1)r[i]=s[i]-'a'+1;
        rep(i,1,n)aca.insert(r+pos[i]-1,len[i]);
        aca.build();
        rep(i,1,n)
        {
            int p=1;
            rep(j,0,len[i]-1)
                p = aca.move(p,r[pos[i]+j]);
            ans+=aca.w[p];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

本文地址:https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/107344377