텍스트가 있다고 가정해 보겠습니다. 다음과 같이 a[1], a[2], ..., a[k]가 존재하는 가능한 가장 큰 k를 찾아야 합니다. 각 a[i]는 공백이 아닌 문자열입니다. 그리고 연결 a[1] + a[2] + ... + a[k]는 주어진 텍스트와 같습니다. 범위 1에서 k까지의 모든 i에 대해 a[i] =a[{k+1 - i}].
따라서 입력이 text ="antprezatepzapreanta"와 같으면 "a|nt|a|pre|za|tpe|za|pre|a|nt|a"와 같이 분할할 수 있기 때문에 출력은 11이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
카운터 :=0
-
i :=1, j :=텍스트 크기 - 1
-
ic :=0, jc :=텍스트 크기
-
동안 나는 <=j, 수행
-
텍스트의 하위 문자열[인덱스 ic에서 i-1까지]이 텍스트의 하위 문자열[인덱스 j에서 jc-1까지]과 동일한 경우
-
카운터 :=카운터 + 2
-
ic :=나는
-
jc :=j
-
-
나는 :=나는 + 1
-
j :=j - 1
-
-
ic이 jc와 같지 않으면
-
카운터 :=카운터 + 1
-
-
반환 카운터
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(text):
counter = 0
i, j = 1, len(text) - 1
ic, jc = 0, len(text)
while i <= j:
if text[ic:i] == text[j:jc]:
counter += 2
ic = i
jc = j
i += 1
j -= 1
if ic != jc:
counter += 1
return counter
text = "antaprezatepzapreanta"
print(solve(text)) 입력
[3,4,5,2,1,7,3,4,7], 3
출력
11