题解
AC自动机
学了一天之后，终于想明白了一件事：
为什么有时候按照AC图的递推形式不用$fail$?
因为在$buildfail$的时候，已经利用了“指向的点要打上同样结束标记的性质”。
这样貌似就无形之中运用了$fail$数组。
真是神奇的东西啊。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using namespace std;
typedef long long ll;
int n,m,que[10005],f,r;
char T[10005],tmp[10005];
int trie[10005][26]={0},cnt=0;
int val[10005];
int fail[10005],SIG_SIZE=26;
int dp[1005][305]={0};
bool vis[1005][305]={0};
//0->root
void trie_insert(char *a){
int p=0;
for(;*a;a++){
if(!trie[p][*a-'A'])
trie[p][*a-'A']=++cnt;
p=trie[p][*a-'A'];
}
val[p]++;
}
void getFail(){
f=r=0,fail[0]=0;
for(int i=0;i<SIG_SIZE;i++){
int h=trie[0][i];
if(h)
fail[h]=0,que[r++]=h;
}
while(r-f){
int h=que[f++],i,_v,f;
for(i=0;i<SIG_SIZE;i++){
_v=trie[h][i];
if(!_v){
trie[h][i]=trie[fail[h]][i];
continue;
}
que[r++]=_v,f=fail[h];
for(;f&&!trie[f][i];f=fail[f]);
fail[_v]=trie[f][i];
val[_v]+=val[fail[_v]];//
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",tmp),trie_insert(tmp);
getFail();
for(int i=0;i<=m;i++)
for(int j=0;j<=cnt;j++)
dp[i][j]=-2000000000;
dp[0][0]=0;
for(int i=1;i<=m;i++){
for(int j=0;j<=cnt;j++){
int x;
for(int k=0;k<3;k++){
x=trie[j][k];
dp[i][x]=max(dp[i][x],dp[i-1][j]+val[x]);
}
}
}
int ans=0;
for(int i=0;i<=cnt;i++)
ans=max(ans,dp[m][i]);
printf("%d\n",ans);
return 0;
}