Find Kammyu

一つ目の答え

$1\le i\le|S|-5$ なる全ての $i$ について $S_iS_{i+1}S_{i+2}S_{i+3}S_{i+4}S_{i+5}$ が kammyu に一致するかを判定すればよいです。
適切に実装することで $O(N)$ で解くことができます。

二つ目の答え

$dp[i][j]=S$ の $i$ 文字目までの文字列 $S_1S_2\cdots S_{i-1}S_i$ に部分列として現れる kammyu の $j$ 文字目までの個数

とします。つまり、

• $dp[i][1]=S$ の $i$ 文字目までの文字列 $S_1S_2\cdots S_{i-1}S_i$ に部分列として現れる k の個数
• $dp[i][2]=S$ の $i$ 文字目までの文字列 $S_1S_2\cdots S_{i-1}S_i$ に部分列として現れる ka の個数
• $dp[i][3]=S$ の $i$ 文字目までの文字列 $S_1S_2\cdots S_{i-1}S_i$ に部分列として現れる kam の個数
• $dp[i][4]=S$ の $i$ 文字目までの文字列 $S_1S_2\cdots S_{i-1}S_i$ に部分列として現れる kamm の個数
• $dp[i][5]=S$ の $i$ 文字目までの文字列 $S_1S_2\cdots S_{i-1}S_i$ に部分列として現れる kammy の個数
• $dp[i][6]=S$ の $i$ 文字目までの文字列 $S_1S_2\cdots S_{i-1}S_i$ に部分列として現れる kammyu の個数

です。
ここで、求めたい答えは $dp[N][6]$ です。

$dp[i][1]$ は $i$ 文字目までに存在する k の個数と同じです。
$dp[i][j]$ は $S_j$ と $dp[i-1][j]$ と $dp[i][j-1]$ から求めることができます。

（実装例では、補助として空文字列の個数 $dp[0][0]=dp[1][0]=\dots=dp[N][0]=1$ を導入しています。）
（そして、$i$ の昇順に求めており、実装例の中での dp[j] は本解説では $dp[i][j]$ と対応します。）

以上を適切に実装することで $O(N)$ で解くことができます。

実装例（C++）

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#include <bits/stdc++.h>
using namespace std;
int main()
{
  string S;
  cin >> S;
  string kammyu = "kammyu";

  int ans1 = 0;
  for (int i = 0; i < S.length() - 5; i++)
  {
    bool f = true;
    for (int j = 0; j < 6; j++)
      f &= S[i + j] == kammyu[j];
    ans1 += f;
  }
  cout << ans1 << endl;

  int dp[7] = {1};
  for (char c : S)
  {
    for (int j = 6; j > 0; j--)
      if (c == kammyu[j - 1])
        dp[j] = (dp[j] + dp[j - 1]) % 998244353;
  }
  cout << dp[6] << endl;
}