문자열 str이 제공된다고 가정합니다. 문자열의 경계는 해당 문자열의 적절한 접두사와 접미사인 부분 문자열입니다. 예를 들어, 'ab'는 문자열 'ababab'의 테두리입니다. 테두리 문자열이 회문이면 테두리를 회문 테두리라고 합니다. 이제 주어진 문자열 str에 회문 경계가 f(str)개 있다고 가정합니다. str의 비어 있지 않은 모든 부분 문자열 str_k에 대한 f(str_k)의 합을 찾아야 합니다. 합이 클 수 있으므로 모듈로 연산은 10^9 + 7로 수행할 수 있습니다.
따라서 입력이 str ='pqpqp'와 같으면 출력은 5가 됩니다. 'pqpqp' 문자열의 하위 문자열이 15개 존재합니다. 그러나 4개의 하위 문자열에만 회문 경계가 있습니다. 문자열은 다음과 같습니다.
pqp : f(pqp) = 1 pqpqp : f(pqpqp) = 2 qpq : f(qpq) = 1 pqp : f(pqp) = 1 The sum of these values are 1 + 2 + 1 + 1 = 5.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- palindrome_calculator() 함수를 정의합니다. 이것은 input_dict
- 을 취합니다.
- ans :=0
- 각 item1, input_dict 값의 item2에 대해 do
- ans :=ans + item2 *((item2 - 1) / 2의 하한 값
- 반환
- str_check() 함수를 정의합니다. 이것은 string
- 을 취합니다.
- t_str :=문자열[0]
- 문자열의 각 s에 대해 다음을 수행합니다.
- s가 t_str과 같지 않으면
- 거짓을 반환
- 참 반환
- s가 t_str과 같지 않으면
- string_res() 함수를 정의합니다. 이것은 string
- 을 취합니다.
- ans :=0
- 범위 2에서 문자열 크기 + 1까지의 i에 대해
- ans :=ans + i *((i - 1) / 2의 하한 값
- ans :=as mod 1000000007
- 반환 및
- str_check(string)이 True이면
- string_res(문자열)를 반환
- ans :=0
- odd_list :=새 목록, 새 지도 및 1을 포함하는 새 목록
- 문자열의 각 s에 대해 다음을 수행합니다.
- s가 odd_list[1]에 없으면
- 홀수_목록[1, s] :=0
- odd_list[1, s] :=odd_list[1, s] + 1
- s가 odd_list[1]에 없으면
- 0~문자열 크기 범위의 i에 대해
- odd_list[0] 끝에 i 삽입
- ans :=ans + palindrome_calculator(odd_list[1])
- even_list :=새 목록, 새 지도 및 1을 포함하는 새 목록
- 0에서 문자열 크기 - 1 사이의 i에 대해
- 문자열[i]가 문자열[i + 1]과 같으면
- even_list[0] 끝에 i 삽입
- tmp :=string[인덱스 i에서 i + 2까지]
- even_list[1]에 tmp가 없으면
- even_list[1, tmp] :=0
- even_list[1, tmp] :=even_list[1, tmp] + 1
- 문자열[i]가 문자열[i + 1]과 같으면
- ans :=ans + palindrome_calculator(even_list[1])
- 범위 3에서 문자열 크기까지의 val에 대해
- val mod 2가 0과 같으면
- wt :=even_list
- 그렇지 않으면
- wt :=odd_list
- new_t :=새 목록, 새 지도 및 값을 포함하는 새 목록
- wt[0]의 각 인덱스에 대해
- index - 1>=0이고 index + val - 2
- 인덱스 삽입 - new_t[0] 끝에 1
- tmp :=string[인덱스 인덱스 - 1에서 인덱스 - 1 + val까지]
- tmp가 new_t[1]에 없으면
- new_t[1, tmp] :=0
- new_t[1, tmp] :=new_t[1, tmp] + 1
- index - 1>=0이고 index + val - 2
- val mod 2가 0과 같으면
- ans :=ans + palindrome_calculator(new_t[1])
- ans :=as mod 1000000007
- val mod 2가 0과 같으면
- even_list :=new_t
- 그렇지 않으면
- odd_list :=new_t
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def palindrome_calculator(input_dict):
ans = 0
for item1, item2 in input_dict.items():
ans += item2 * (item2 - 1) // 2
return ans
def str_check(string):
t_str = string[0]
for s in string:
if s != t_str:
return False
return True
def string_res(string):
ans = 0
for i in range(2, len(string) + 1):
ans += i * (i - 1) // 2
ans %= 1000000007
return ans
def solve(string):
if str_check(string):
return string_res(string)
ans = 0
odd_list = [[], {}, 1]
for s in string:
if s not in odd_list[1]:
odd_list[1][s] = 0
odd_list[1][s] += 1
for i in range(len(string)):
odd_list[0].append(i)
ans += palindrome_calculator(odd_list[1])
even_list = [[], {}, 1]
for i in range(len(string) - 1):
if string[i] == string[i + 1]:
even_list[0].append(i)
tmp = string[i:i + 2]
if tmp not in even_list[1]:
even_list[1][tmp] = 0
even_list[1][tmp] += 1
ans += palindrome_calculator(even_list[1])
for val in range(3, len(string)):
if val % 2 == 0:
wt = even_list
else:
wt = odd_list
new_t = [[], {}, val]
for index in wt[0]:
if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
new_t[0].append(index - 1)
tmp = string[index - 1 : index - 1 + val]
if tmp not in new_t[1]:
new_t[1][tmp] = 0
new_t[1][tmp] += 1
ans += palindrome_calculator(new_t[1])
ans %= 1000000007
if val % 2 == 0:
even_list = new_t
else:
odd_list = new_t
return ans
print(solve('pqpqp')) 입력
'pqpqp'
출력
5