禁止字符串

发表于 |

题目

给一个长度为$K$的只包含$A,T,C,G$四个字符的字符串$S$，求长度恰好为$N$的不包含字符串$S$的字符串的个数。输出个数对1009取模的结果。

数据范围

$1\leq K\leq 100,1\leq N\leq10000$

做法

$dp[i][j]:=$以$S$的最长长度为$j$的前缀为后缀的长度为$i$的字符串的个数。
先用$fail[]$数组预处理出$dp$的状态转移表，单后直接$dp$。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAX_LEN_P = 100;  // 模式串的最大长度
const int MAX_N = 100;      // N的最大值
const int mod = 10009;
const char *AGCT = "AGCT";  // 字符集
char p[MAX_LEN_P];          // 模式串
int dp[MAX_N][MAX_LEN_P];   // dp[i][j]:=前i个字符中后缀与p的前缀的最大匹配长度为j的字符串个数
int nxt[MAX_LEN_P][4];      // 状态转移表
int fail[MAX_LEN_P];        // p串的fail指针
int N, K;                   // K为模式串的长度
void GetFail(char p[])
{
  int k = -1;
  fail[0] = -1;
  for (int i = 1; p[i]; ++i) {
    while (k >= 0 && p[k + 1] != p[i]) k = fail[k];
    if (p[k + 1] == p[i]) k++;
    fail[i] = k;
  }
}
void Solve()
{
  GetFail(p);
  // 预处理状态转移表
  for (int i = 0; i < 4; ++i) {
    if (AGCT[i] == p[0]) nxt[0][i] = 1;
    else nxt[0][i] = 0;
  }
  for (int i = 1; i < K; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (AGCT[j] == p[i]) {
        nxt[i][j] = i + 1;
      } else {
        int k;
        for (k = fail[i - 1]; k >= 0 && p[k + 1] != AGCT[j]; k = fail[k]);
        if (p[k + 1] == AGCT[j]) ++k;
        nxt[i][j] = k + 1;
      }
    }
  }
  // 多组小数据时，for循环初始化比memset快
  memset(dp, 0, sizeof dp);
  dp[0][0] = 1;
  for (int i = 0; i < N; ++i) {
    // for (int j = 0; j < K; ++j) dp[i][j] = 0;
    for (int j = 0; j < K; ++j) {
      for (int k = 0; k < 4; ++k) {
        int nt = nxt[j][k];
        if (nt == K) continue;
        dp[i + 1][nt] = (dp[i + 1][nt] + dp[i][j]) % mod;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < K; ++i) ans = (ans + dp[N][i]) % mod;
  printf("%d\n", ans);
}
int main()
{
  cin >> N >> K;
  scanf("%s", p);
  Solve();
  return 0;
}