let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

QBPAL - Đếm chuỗi đối xứng

solution.md

Gọi \(S\) là chuỗi đầu vào. Gọi \(F(l, r)\) là số dãy con đối xứng trong đoạn từ \(l\) đến \(r\). Kết quả bài toán là \(F(1, n)\).

Ta có công thức QHĐ sau:

\[F(l, r) = \begin{cases} F(l+1, r) + F(l, r-1) - F(f+1, r-1) & \text{if } S(l) \ne S(r) \\ F(l+1, r) + F(l, r-1) - F(f+1, r-1) \\ + 1 + F(f+1, r-1) & \text{if } S(l) = S(r) \\ \end{cases}\]

Giải thích:

  • Khi \(S(l) \ne S(r)\), ta tính \(F(l, r)\) từ 2 trường hợp con \(F(l+1, r)\) và \(F(l, r-1)\), cần trừ đi \(F(l+1, r-1)\) để loại bỏ những trường hợp trùng (tương tự như công thức giao tập hợp \(|A \cup B| = |A| + |B| - |A \cap B|\)).
  • Khi \(S(l) = S(r)\), ta cần cộng thêm \(1 + F(l+1, r-1)\) để tính những dãy con đối xứng bắt đầu ở \(S(l)\) và kết thúc ở \(S(r)\).

Để cài đặt công thức này, cần lặp \(l\) từ \(n\) về 1 và \(r\) từ \(l\) đến \(n\). Code dưới dùng đệ quy có nhớ cho đơn giản.

Cần cài đặt xử lý số lớn (cộng và trừ) khi dùng C++.

main.py
Open in Github • Download 
s = input()
N = len(s)

f = [[0 for j in range(N)] for i in range(N)]

def calc(l, r):
    if f[l][r] != -1:
        return f[l][r]

    if l == r:
        f[l][r] = 1
        return f[l][r]
    elif l > r:
        f[l][r] = 0
        return f[l][r]

    f[l][r] = calc(l, r-1) + calc(l+1, r) - calc(l+1, r-1)
    if s[l] == s[r]:
        f[l][r] += 1 + calc(l+1, r-1)
    return f[l][r]

print(calc(0, N-1))
Comments