結果

問題 No.2172 SEARCH in the Text Editor
ユーザー LyricalMaestro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

## 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()
0