GeT AC

1. GeT AC

問題

A, C, G, T からなる長さNの文字列 Sが与えられます。以下の Q個の問いに答えてください。問 i (1≤i≤Q): 整数 li,ri (1≤li
Sの先頭から li 文字目から ri 文字目までの (両端含む) 部分文字列を考える。この文字列に AC は部分文字列として何回現れるか。

こう考えた

• countでACの数を計算して出力する。

書いたコード

N,Q=map(int,input().split())
S=input()
for q in range(Q):
  l,r=map(int,input().split())
  s=S[l-1:r]
  print(s.count("AC"))

🐍これでいけんちゃうかな？

結果

TLE

🐍計算量の問題か

Atcoderの標準回答

N,Q=map(int,input().split())
S=input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for q in range(Q):
  l,r=map(int,input().split())
  print(t[r-1] - t[l-1])

🐍ACのカウントの配列をつくるんやな。

結果

AC

🐍文字列検索って結構時間喰うねんな。。