Giả sử chúng ta có một chuỗi ký tự viết thường (tất cả đều là ký tự ASCII), chúng ta phải tìm tất cả các chuỗi con palindromic liên tục riêng biệt của chuỗi đã cho.
Vì vậy, nếu đầu vào giống như "level", thì đầu ra sẽ là 7 vì có bảy chuỗi con ['level', 'eve', 'l', 'e', 'v', 'e', 'l' ].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
N:=26
-
n:=chiều dài của str
-
tổng:=0
-
my_map:=danh sách kích thước N và điền bằng 0
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
my_map [ASCII of (str [i]) - ASCII of ('a')]:=my_map [ASCII of (str [i]) - ASCII of ('a')] + 1
-
-
đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện
-
nếu my_map [i] khác 0 thì
-
sum:=sum + (my_map [i] * (my_map [i] + 1) / 2)
-
-
-
trả lại số tiền
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
N = 26
def all_palindrome_substr_count(str):
n = len (str)
sum = 0
my_map = [0] * N
for i in range(n):
my_map[ord(str[i]) - ord('a')] += 1
for i in range(N) :
if (my_map[i]):
sum += (my_map[i] * (my_map[i] + 1) // 2)
return sum
str = "level"
print (all_palindrome_substr_count(str)) Đầu vào
"level"
Đầu ra
7