[NOIP2015 提高组] 子串

算法

状态定义

最初显然可以想到
\(f[i][j][k]\) 表示 \(A\) 串前 \(i\) 个, \(B\) 串前 \(j\) 个, 分割了 \(k\) 个子串
但是这样无法递推 \(k\) 维

于是加上一位 \(f[i][j][k][0/1]\), 最后一维表示是否选择 \(A\) 子串当前这一位, 也就可以递推的计算

状态转移

• 当前位置不使用
  \(f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]\), 显然

• 当前位置使用
  \(f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1] \leftarrow (a[i]==b[j])\)

边界条件

• 对于A子串前i位，匹配B串第1个字符，那么只可能使用1个字符串，这种情况如果第i位不进行匹配，那么方案数就是之前所有能与第1位匹配的字符，所以 \(f[i][1][1][0]=sum(a[1~i-1]==b[1])\)

• 同上，但如果B串第一位和A串某一位匹配了话，那么 \(f[i][1][1][1]=1\) 是显然的

答案

即为 \(f[n][m][k][0/1]\)

空间复杂度优化

一眼滚动数组

  for (int i=1;i<=n;i++){swap(now,pre); //交换，只要i改变f[now][1][1][0]=s;//边界1if (a[i]==b[1]) f[now][1][1][1]=1,s++;//边界2，解决了s统计的问题for (int j=2;j<=m;j++){for (int k=1;k<=t;k++){if (a[i]==b[j]){f[now][j][k][1]=((f[pre][j-1][k-1][1]+f[pre][j-1][k][1])%prime+f[pre][j-1][k-1][0])%prime;}//方程2f[now][j][k][0]=(f[pre][j][k][0]+f[pre][j][k][1])%prime;//方程1}}for(int j=1;j<=m;j++)for(int k=1;k<=t;k++)f[pre][j][k][1]=f[pre][j][k][0]=0;//清空}

总结

状态的设计可以从需要递推的项中找灵感
注意初始值一般为一行或一个点