题目大意：
给定一些开心串，每个串有一个开心值，构造一个串，每包含一次开心串就会获得一个开心值，求最大获得多少开心值。
题解：
首先先建立AC自动机。（建立fail指针的时候，对val要进行累加）
然后在AC自动机上跑dp
dp[i][j] = max(dp[i][j], dp[i-1][k] + v[j])
写成矩阵形式就是（Mat[i][j]表示从i到j最大获得的开心值）
C[i][j] = max(C[i][j], A[i][k]+B[k][j])
然后这个形式也可以用快速幂的形式加速！！
然后救过了！
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = , maxc = ;
char str[];
struct Trie{
int Next[N][maxc], fail[N], tag[N];
long long val[N];
int root, L;
int newnode(){
for(int i = ; i < maxc; i++)
Next[L][i] = -;
tag[L++] = ;
return L-;
}
void init() { L = ; root = newnode(); }
void Insert(char* s, int len, int v){
int u = root;
for(int i = ; i < len; i++){
int c = s[i] - 'a';
if(Next[u][c] == -) Next[u][c] = newnode();
u = Next[u][c];
}
tag[u] = ;
val[u] += v;
}
void build(){
queue<int> Q;
fail[root] = root;
for(int i = ; i < maxc; i++){
if(Next[root][i] == -) Next[root][i] = root;
else {
fail[Next[root][i]] = root;
Q.push(Next[root][i]);
}
}
while(!Q.empty()){
int u = Q.front();
Q.pop();
val[u] += val[fail[u]];
for(int i = ; i < maxc; i++){
int &v = Next[u][i];
if(v == -){
v = Next[fail[u]][i];
} else {
Q.push(v);
fail[v] = Next[fail[u]][i];
}
}
}
}
}ac; struct Matrix{
long long Mat[][];
int n;
Matrix() {n = ; memset(Mat, , sizeof(Mat));}
Matrix(Matrix &B){
n = B.n;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
Mat[i][j] = B.Mat[i][j];
}
Matrix operator +(const Matrix &B)const {
Matrix C;
C.n = n;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++){
C.Mat[i][j] = -1e18;
for(int k = ; k <= n; k++)
C.Mat[i][j] = max(C.Mat[i][j], Mat[i][k] + B.Mat[k][j]);
}
return C;
}
void print(){
cout<<"*"<<endl;
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++) cout<<Mat[i][j]<<" ";
cout<<endl;
}
}
}A;
Matrix mypow(Matrix A, long long b)
{ Matrix ans = A; b--; for(; b; b >>= , A = A+A) if(b&) ans = ans+A; return ans;}
int n, val[];
long long l;
int main()
{
ac.init();
cin>>n>>l;
for(int i = ; i <= n; i++) scanf("%d", &val[i]);
for(int i = ; i <= n; i++){
cin>>str;
ac.Insert(str, strlen(str), val[i]);
}
ac.build();
A.n = ac.L-;
for(int i = ; i < ac.L; i++)
for(int j = ; j < ac.L; j++)
A.Mat[i][j] = -1e18;
for(int i = ; i < ac.L; i++){
for(int j = ; j < maxc; j++){
int v = ac.Next[i][j];
if(v == -) continue;
A.Mat[i][v] = ac.val[v];
}
}
A = mypow(A, l);
long long ans = -1e18;
for(int i = ; i < ac.L; i++) ans = max(ans, A.Mat[][i]);
cout<<ans<<endl;
return ;
}