求教!如果我把方程写成这样要怎么想到矩阵做法

回复帖子

@smzzl 2018-10-11 23:20 回复

如题,加(如果我把方程写成这样要怎么想到矩阵做法以及我要怎么转换我这个方程至可以用矩阵乘法的式子)

for (int i=1;i<=n;i++)
    for (int dig=0;dig<=9;dig++)
        for (int done=-1;done<=m-2;done++)
          {
            int j=done+1;
            while (j>0 && st[j]-'0'!=dig) j=_next[j];
            if (st[j]-'0'==dig) dp[i][j+N]+=dp[i-1][done+N];
            if (st[j]-'0'!=dig) dp[i][-1+N]+=dp[i-1][done+N];
          }

以上我的代码中dp部分,其中j是跳kmp用的。(为了代码简介删去了模操作)

方程意思是dp[i][j]表示:

我长串到第i位,匹配串匹配到了第j个,并且长串最后j位匹配住了匹配串的方案数(这个设置同常规做法)

但是我转移的方法是枚举我这一位的数字(dig),然后枚举上一位匹配到匹配串的第几个位置(done,done=1表示都未匹配到,+N是因为数组不能开下界)

我这个代码已经过测试拿到了暴力dp的40分,正确性没有问题。但是这样的话,好像就不太好看怎么用矩阵加速了(大概是本人太菜了看不出来)

希望有大佬指点迷津,谢谢