Sub 1 + Sub 2:

Với mỗi truy vấn, xét toàn bộ các xâu con liên tiếp nằm trong đoạn ~[l, r]~. Với mỗi xâu nằm trong đoạn như vậy, kiểm tra xem nó có phải xâu đối xứng không.

ĐPT: ~q * n^{3}~, với n là độ dài xâu s.

Sub 3:

Đầu tiên, ta chuẩn bị trước một mảng bool ~palin[l][r]~ mang giá trị ~0 / 1~;

• ~palin[l][r] = 1~ nếu xâu con liên tiếp từ ~l~ đến ~r~ là một xâu đối xứng.
• ~palin[l][r] = 0~ nếu xâu con liên tiếp từ ~l~ đến ~r~ không phải là một xâu đối xứng.

Sử dụng ý tưởng mạng cộng dồn hai chiều, ta coi một ma trận nhị phân ~n x n~, ô ~[i][j] = 0/1~ với ý nghĩa xâu con từ ~i~ đến ~j~ có phải một xâu đối xứng không;

Với mỗi truy vấn, sử dụng công thức tính tổng một bảng con trong bảng lớn của mảng cộng dồn 2 chiều với độ phức tạp ~O(1)~.

ĐPT: ~n^{3} + q~.

Sub 4:

Ta cũng chuẩn bị trước một mảng ~palin[l][r]~ nhưng với độ phức tạp ~O(n^{2})~.

Tính ~palin[l][r]~ với ~r - l~ tăng dần.

Vậy ~palin[i][j] = palin[i+1][j-1]~ && ~(s[i] == s[j])~

Từ đây, ta gọi dp[i][j] là số xâu đối xứng liên tiếp trong đoạn ~[i, j]~.

Cũng tính với ~j - i~ tăng dần, vậy ~dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + palin[i][j]~.

ĐPT: ~n^2 + q~