สมมติว่าเรามีสตริง s เราต้องหาจำนวนอักขระขั้นต่ำที่จะแทรกหลังจาก s เพื่อให้เป็นพาลินโดรม
ดังนั้น หากอินพุตเป็น s ="mad" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถเติม "am" เพื่อให้เป็น "mad" ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
b :=256, m :=10^9 + 7
-
s :=รายการโดยนำความแตกต่างของ (ASCII ของ i) − 97 สำหรับแต่ละ i ใน s
-
r :=องค์ประกอบสุดท้ายของ s, l :=องค์ประกอบสุดท้ายของ s
-
n :=ขนาดของ s
-
res :=n − 1
-
p :=b
-
สำหรับฉันอยู่ในช่วง n − 2 ถึง 0, ลดลง 1 ทำ
-
r :=r + s[i] * p, r :=r mod m
-
l :=l * b, l :=l + s[i]
-
l :=l mod m
-
p :=p * b, p :=p mod m
-
ถ้า l เหมือนกับ r แล้ว
-
res :=ผม
-
-
-
ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
