中等的字符串 [Ac自动机, 矩阵乘法(max)]

$中等的字符串$

---

$color{red}{正解部分}$

建出 $Ac$ 自动机, 在自动机上 $dp$,

设 $F[i, j]$ 表示 $i$ 节点走 $j$ 步所能得到的 最大值,
则 $F[i, j] = max(F[to, j-1] + w_{to})$, 时间复杂度 $O(NM^2)$ .

继续优化, 建立两个矩阵如下

$egin{bmatrix} F_{1,0} F_{2,0}, F_{3,0} ... F_{tot,0}end{bmatrix}$

$egin{bmatrix} -inf -inf-inf ... -inf\ w_{a} w_{a} w_{a} ... w_{a} \w_{b} w_{b} w_{b} ... w_{b} \ . \ . \ . \ -inf -inf-inf ... -inf end{bmatrix}$

将两个矩阵相乘, 将加法替换为 $max$ 操作, 乘法替换为加法,
可以得到 $[F_{1,1} = max(F_{1,0}-inf, F_{1,0}+w_1,...,F_{1,0} + w_{tot}), ...F_{tot,1}]$ .

于是矩阵 $2$ 的 $N$ 次幂乘上 矩阵 $1$ 即可得到答案矩阵 .

---

$color{red}{实现部分}$

• 注意 单位矩阵 为 $egin{bmatrix} 0 -inf ... -inf \ -inf 0 ... -inf \ ............... \ -inf -inf ... 0end{bmatrix}$

#include<bits/stdc++.h>
#define reg register
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef std::pair<ll, int> pr;

const int maxn = 100004;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int M;
int A[maxn];
int dep[maxn];
int node_cnt;

ll N;
ll F[20004][105];

bool vis[maxn];

char Smp[205];

std::vector <int> Mp[27];

struct Node{ int nxt, ch[30], p; } Trie_t[maxn];

void Add(char *s, int x){
        int len = strlen(s), cur = 0;
        for(reg int i = 0; i < len; i ++){
                int t = s[i];
                if(!Trie_t[cur].ch[t-'a']){
                        Trie_t[cur].ch[t-'a'] = ++ node_cnt;
                        Mp[t-'a'].pb(node_cnt);
                        dep[node_cnt] = dep[cur] + 1;
                }
                cur = Trie_t[cur].ch[t-'a'];
        }
        Trie_t[cur].p += x;
}

void Build_Ac(){
        std::queue <int> Q;
        for(reg int i = 0; i < 26; i ++) if(Trie_t[0].ch[i]) Q.push(Trie_t[0].ch[i]);
        while(!Q.empty()){
                int ft = Q.front(); Q.pop();
                Trie_t[ft].p += Trie_t[Trie_t[ft].nxt].p;
                for(reg int i = 0; i < 26; i ++){
                        int &to = Trie_t[ft].ch[i];
                        if(to) Trie_t[to].nxt = Trie_t[Trie_t[ft].nxt].ch[i], Q.push(to);
                        else to = Trie_t[Trie_t[ft].nxt].ch[i];
                }
        }
}

struct Matrix{ 
        ll v[205][205]; 
        friend Matrix operator * (const Matrix &a, const Matrix &b){
                Matrix s;
                for(reg int i = 1; i <= node_cnt+1; i ++)
                        for(reg int j = 1; j <= node_cnt+1; j ++) s.v[i][j] = -inf;
                for(reg int i = 1; i <= node_cnt+1; i ++)
                        for(reg int j = 1; j <= node_cnt+1; j ++)
                                for(reg int k = 1; k <= node_cnt + 1; k ++) 
                                        s.v[i][j] = std::max(s.v[i][j], a.v[i][k]+b.v[k][j]);
                return s;
        }
} P, I;

Matrix Ksm(Matrix a, ll b){
        Matrix s;
        for(reg int i = 1; i <= node_cnt+1; i ++)
                for(reg int j = 1; j <= node_cnt+1; j ++) s.v[i][j] = (i==j)?0:-inf;
        while(b){ if(b & 1) s = s * a; a = a * a; b >>= 1; }
        return s;
}

void Fuck(){ 
        for(reg int i = 1; i <= node_cnt+1; i ++)
                for(reg int j = 1; j <= node_cnt+1; j ++) P.v[i][j] = -inf;

        for(reg int i = 1; i <= node_cnt+1; i ++) P.v[1][i] = 0;
        I.v[1][1] = -inf;
        for(reg int i = 1; i <= node_cnt+1; i ++)
                for(reg int j = 1; j <= node_cnt+1; j ++) I.v[i][j] = -inf;
        for(reg int u = 0; u <= node_cnt; u ++)
                for(reg int i = 0; i < 26; i ++)
                        I.v[Trie_t[u].ch[i]+1][u+1] = Trie_t[Trie_t[u].ch[i]].p;
        I = Ksm(I, N); P = P * I;
        printf("%lld
", P.v[1][1]);
}

int main(){
        scanf("%lld%d", &N, &M);
        for(reg int i = 1; i <= M; i ++) scanf("%d", &A[i]);
        for(reg int i = 1; i <= M; i ++){ scanf("%s", Smp); Add(Smp, A[i]); } 
        Build_Ac(); Fuck();
        return 0;
}