結果
問題 |
No.2172 SEARCH in the Text Editor
|
ユーザー |
|
提出日時 | 2024-12-17 02:32:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 610 ms / 2,000 ms |
コード長 | 2,570 bytes |
コンパイル時間 | 346 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 132,948 KB |
最終ジャッジ日時 | 2024-12-17 02:32:31 |
合計ジャッジ時間 | 15,340 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
## https://yukicoder.me/problems/no/2172 MOD = 998244353 def new_s(T, s): t_count = 0 if len(s) >= len(T): for i in range(len(s) + 1 - len(T)): s_ = s[i:(i + len(T))] if s_ == T: t_count += 1 left = s if (len(s) < len(T)) else s[:(len(T) - 1)] right = s if (len(s) < len(T)) else s[-(len(T) - 1):] return (t_count, left, right) def main(): N = int(input()) T = input() steps = [] for _ in range(N): values = input().split() steps.append(values) if len(T) >= 2: s_array = [] for step in steps: if len(step) == 1: s = step[0] s_array.append(new_s(T, s)) else: _, j, k = step j = int(j) - 1 k = int(k) - 1 tj_count, j_left, j_right = s_array[j] tk_count, k_left, k_right = s_array[k] t_count = (tj_count + tk_count) % MOD for j in range(len(j_right)): j_ = j_right[j:] k = len(j_right) - j if len(k_left) >= len(T) - k: k_ = k_left[:(len(T) - k)] ans = j_ + k_ if ans == T: t_count += 1 t_count %= MOD if j_left == j_right: s = (j_left + k_left) left = s if (len(s) < len(T)) else s[:(len(T) - 1)] else: left = j_left if k_left == k_right: s = (j_right + k_right) right = s if (len(s) < len(T)) else s[-(len(T) - 1):] else: right = k_right s_array.append((t_count, left, right)) ans, _, _ = s_array[-1] print(ans) else: s_array = [] for step in steps: if len(step) == 1: s = step[0] t_count = 0 for s_ in s: if s_ == T: t_count += 1 s_array.append(t_count) else: _, j, k = step j = int(j) - 1 k = int(k) - 1 t_count = s_array[j] + s_array[k] t_count %= MOD s_array.append(t_count) ans = s_array[-1] print(ans) if __name__ == "__main__": main()