牛客小白赛54 E

大家都知道 KMPAM 吧？

对这题，考虑一个 dp 套 dp。

内层为你目前在 KMP 自动机上的位置，外层为到当前点已经匹配了多少个。

顺着 KMPAM 转移边的方向转移即可。

p.s. KMPAM 就是 KMP 匹配的过程写成自动机的形式，使得可以 $O(1)O(1)$ 转移。

上代码~

// KMPAM
// wa 了 qwq

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
uint A[105][26],Pre[105];chr C[105];
int QwQ[105][105],Last[105];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    uint n,m,l;scanf("%u%u%s",&n,&m,C),l=0;while(C[l])l++;
    for(uint i=0,j=-1;i<l;i++)
    {
        while(~j&&C[i]!=C[j+1])j=Pre[j];
        if(i&&C[i]==C[j+1])j++;
        Pre[i]=j;for(uint k=0;k<26;k++)A[i][k]=~j?A[j][k]:A[0][k];
        A[i][C[i]-'a']=i+1;
    }
    for(uint j=0;j<m;j++)for(uint k=0;k<l;k++)QwQ[j][k]=-1e5;
    QwQ[0][0]=0;
    for(uint i=0;i<n;i++)
    {
        scanf("%s",C);
        for(uint j=0;j<m;j++)
        {
            for(uint k=0;k<l;k++)Last[k]=QwQ[j][k],QwQ[j][k]=-1e5;
            for(uint k=0;k<l;k++)_max(QwQ[j][A[k][C[j]-'a']%l],Last[k]+(int)(A[k][C[j]-'a']/l));
            if(j)for(uint k=0;k<l;k++)_max(QwQ[j][A[k][C[j]-'a']%l],QwQ[j-1][k]+(int)(A[k][C[j]-'a']/l));
        }
    }
    int ans=0;for(uint i=0;i<l;i++)_max(ans,QwQ[m-1][i]);
    printf("%d\n",ans);return 0;
}