問題一覧 > 通常問題

No.2172 SEARCH in the Text Editor

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : 👑 NachiaNachia / テスター : NyaanNyaanNyaanNyaan
1 ProblemId : 8881 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-23 12:26:28

問題文

始めに文字列 $T$ が与えられます。

その後、 $N$ 個の文字列 $S_1,S_2,\ldots ,S_N$ の生成過程が与えられます。 生成過程は $N$ ステップからなり、$S_1$ から $S_N$ の順に $1$ ステップにつき $1$ 個ずつ文字列を生成します。 $i$ 番目のステップは次のいずれかの形式で与えられます。

  • (過程A) ~ 以外の空でない文字列 $s$ が与えられた場合、 $S_i=s$ とする。
  • (過程B) 与えられた文字列が ~ であった場合、追加で $i$ 未満の正整数 $j$ , $k$ が与えられるので、 $S_i$ は $S_j$ と $S_k$ をこの順に連結した文字列とする。

$S_N$ の連続する部分であって $T$ に一致するものの個数を $K$ とします。 $K$ を $998244353$ で割った余りを出力してください。

制約

入力は次の制約を満たします。

  • $N$ は $1$ 以上 $100000$ 以下の整数である。
  • $T$ の文字数 $|T|$ は $1$ 以上 $50$ 以下である。
  • $s$ や $T$ として与えられる文字列に含まれうる文字は、 ASCII 文字のうち、英小文字、英大文字、数字の合計 $62$ 種である。
  • 文字列 $s$ の長さは $1$ 以上である。
  • $s$ として与えられる文字列の長さの合計は $100000$ を超えない。ただし (過程B) の ~ は数えない。
  • $i$ 番目のステップについて、それが (過程B) である場合、 $1\leq j\lt i$
  • $i$ 番目のステップについて、それが (過程B) である場合、 $1\leq k\lt i$

入力

入力は次の形式で与えられます。

$N$
$T$
$\text{step}_1$
$\text{step}_2$
$\vdots$
$\text{step}_N$

$\text{step}_i$ $(1\leq i\leq N)$ は $i$ 番目のステップを表します。次の $2$ 通りの形式のいずれかです。

$s$
~ $j$ $k$

前者は $S_i$ が直接与えられることを表します。後者は $S_i$ が $S_j$ と $S_k$ の連結で定義されることを表します。

出力

$K$ の値を $998244353$ で割った余りを出力したのち、改行してください。

サンプル

サンプル1
入力
2
8Em2d
2dXXXXX8Em2dXXXXX8Em
~ 1 1
出力
3

$S_2=$ 2dXXXXX8Em2dXXXXX8Em2dXXXXX8Em2dXXXXX8Em です。

サンプル2
入力
6
aba
aba
bbaab
b
~ 1 2
~ 4 1
~ 3 5
出力
3

$S_1=$ aba です。

$S_2=$ bbaab です。

$S_3=$ b です。

$S_4=$ ababbaab です。

$S_5=$ ababbaababa です。

$S_6=$ bababbaababa です。

サンプル3
入力
26
a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
~ 1 1
~ 2 2
~ 3 3
~ 4 4
~ 5 5
~ 6 6
~ 7 7
~ 8 8
~ 9 9
~ 10 10
~ 11 11
~ 12 12
~ 13 13
~ 14 14
~ 15 15
~ 16 16
~ 17 17
~ 18 18
~ 19 19
~ 20 20
~ 21 21
~ 22 22
~ 23 23
~ 24 24
~ 25 25
出力
679477247

$K=1677721600$ です。この値を $998244353$ で割った余りは $679477247$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。