문자열 s가 있다고 가정하고 회문을 만들기 위해 s 뒤에 삽입할 최소 문자 수를 찾아야 합니다.
따라서 입력이 s ="mad"와 같으면 출력은 2가 됩니다. "am"을 추가하여 "madam"으로 만들 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
b :=256, m :=10^9 + 7
-
s :=s의 각 i에 대해 (i의 ASCII) − 97의 차를 취한 목록
-
r :=s의 마지막 요소, l :=s의 마지막 요소
-
n :=s
의 크기 -
해상도 :=n − 1
-
피 :=b
-
n − 2에서 0 사이의 i에 대해 1만큼 감소합니다.
-
r :=r + s[i] * p, r :=r 모드 m
-
l :=l * b, l :=l + s[i]
-
l :=l 모드 m
-
p :=p * b, p :=p mod m
-
l이 r과 같으면
-
해상도 :=나는
-
-
-
반환 해상도
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class Solution: def solve(self, s): b = 256 m = 10 ** 9 + 7 s = list(ord(i) − 97 for i in s) r = l = s[−1] n = len(s) res = n − 1 p = b for i in range(n − 2, −1, −1): r += s[i] * p r %= m l *= b l += s[i] l %= m p *= b p %= m if l == r: res = i return res ob = Solution() s = "mad" print(ob.solve(s))
입력
"mad"
출력
2