質問リンク

15770 - QueryreuQ

問題の説明

空の文字列Sの場合

Sの後ろに小文字

を追加
削除

S末尾の文字

実行可能な2つの演算.queryが与えられると、iの1番目の文字がアルファベットであれば、文字列Sに対して1回の演算が行われ、−であれば2回の演算が行われる.
演算を行った後、文字列Sのうち、一部の文字列を書き込む個数を数える.

問題を解く

dpで解く.
queryがqueryrの場合を考えてみましょう.
queryrのフィリンドロン部分文字列はquery의 부분 문자열 개수 + query에 r이 추가됨으로서 생기는 부분 문자열의 개수である.
一般化すると、str1 = str + str[-1]と言ったらn_pellindrom[str1]すなわちstr 1の部分文字列個数はn_pellindrom[str] + str[-1]이 추가돼서 생긴 펠린드롬である.

def ispellindrom(string):
    # 문자열이 추가됨으로서 펠린드롬이 생기는지 검사
    count = 0
    for i in range(len(string)):
        tmp = string[i:]
        left, right = 0, len(tmp)-1
        flag = True

        while left < right:
            if tmp[left] != tmp[right]:
                flag = False
                break
            left  += 1
            right -= 1 
        if flag == True:
            count += 1
    return count

コード全体を以下に示します.

import sys
from collections import defaultdict
input = sys.stdin.readline

Q = int(input())
query = input().strip()
answer = [0 for _ in range(len(query))]
n_pellindrom = defaultdict()
S = ''

def ispellindrom(string):
    # 문자열이 추가됨으로서 펠린드롬이 생기는지 검사
    count = 0
    for i in range(len(string)):
        tmp = string[i:]
        left, right = 0, len(tmp)-1
        flag = True

        while left < right:
            if tmp[left] != tmp[right]:
                flag = False
                break
            left  += 1
            right -= 1 
        if flag == True:
            count += 1
    return count

        
for i in range(len(query)):
    pre = S
    count = 0
    # 연산하기
    if query[i] == '-':
        # 지우기 연산에는 펠린드롬 계산할 필요 x
        S = S[:-1]
    else:
        tmp = 0
        if S != '':
            tmp = n_pellindrom[S]
        S += query[i]
        n_pellindrom[S] = tmp + ispellindrom(S)
    print(n_pellindrom[S], end=' ')