P4591 [TJOI2018]碱基序列 题解

一道字符串&DP好题。

题意

给你一个字符串 $s$，还有 $k$ 组字符串，问你从每组字符串中只选一个字符串，且按顺序排列后连接起来的串为 $s$ 的子串的选择种数有多少个，对 $1\text{e}9+7$ 取模。

题解

显然是道 DP。

定义 $f_{i,j}$ 表示按顺序选到第 $i$ 组串且连接起来的字符串匹配到 $s$ 的第 $j$ 个位置的种数。

显然不是每个状态都能转移到 $f_{i,j}$。当且仅当第 $i$ 组中的某个字符串被 $s$ 从 $j$ 结尾的最后几个字符匹配才能转移，这样就好办了。

用哈希判断就可以了，也可以用 KMP，但我觉得哈希对于这题来说更简单。

代码

#include <cstdio>
#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e4 + 5;
const int K = 1e2 + 5;
const int MOD = 1e9 + 7;
const int BASE = 13331;

string s, a[K][15];
int k, n, c[K], f[K][N];
ULL hs[N], hsh[K][15], pw[N];

void Prework () {
  pw[0] = 1;
  for (int i = 1; i <= n; ++i)
    pw[i] = pw[i - 1] * BASE;
  hs[0] = s[0];
  for (int i = 1; i < n; ++i)
    hs[i] = hs[i - 1] * BASE + s[i];
//  for (int i = 0; i < n; ++i) cout << i << " " << hs[i] << endl;
}

ULL Gethsh (int l, int r) {
  if (!l) return hs[r];
  return hs[r] - hs[l - 1] * pw[r - l + 1];
}

int main() {
  cin >> k >> s;
  n = s.size();
  for (int i = 1; i <= k; ++i) {
    cin >> c[i];
    for (int j = 1; j <= c[i]; ++j) {
      cin >> a[i][j];
      int len = a[i][j].size();
      for (int s = 0; s < len; ++s)
        hsh[i][j] = hsh[i][j] * BASE + a[i][j][s];
//      if (i == 1) {
//        for (int s = 0; s + len - 1 < n; ++s)
//          f[i][s + len - 1] += 1 * (Gethsh(s, s + len - 1) == hsh[i][j]);
//      }
    }
  }
  Prework();
  for (int i = 0; i < n; ++i)
    f[0][i] = 1;
  for (int i = 1; i <= k; ++i)
    for (int j = 1; j <= c[i]; ++j) {
      int len = a[i][j].size();
//      cout << i << " " << j << " " << len << endl;
      for (int s = len - 1; s < n; ++s) {
        f[i][s + 1] = (f[i][s + 1] + (hsh[i][j] == Gethsh(s - len + 1, s)) * f[i - 1][s - len + 1]) % MOD;
//        cout << "***" << hsh[i][j] << " " << Gethsh(s - len + 1, s) << endl;
//        if (hsh[i][j] == Gethsh(s - len + 1, s)) puts("!!!");
      }
    }
  
  int ans = 0;
  for (int i = 0; i < n; ++i)
    ans = (ans + f[k][i + 1]) % MOD;
  cout << ans << endl;
  return 0;
}