Xâu Palind

Nguồn: Đề luyện thi HSG Độ khó: Trung bình Vét cạn Sinh nhị phân Palindrome

Đề bài

Xâu Palindrome (hay còn gọi là xâu đối xứng) là một chuỗi ký tự có tính chất: đọc từ trái sang phải và từ phải sang trái đều giống nhau. Xâu có 1 ký tự cũng được xem là xâu Palindrome.

Xâu con của xâu $S$ là một dãy các ký tự liên tiếp trong xâu $S$.

Phép chia Palind trên xâu $S$ là một cách chia xâu $S$ thành các xâu con liên tiếp. Trong đó, từng xâu con trong cách chia đó đều là xâu Palindrome.

Yêu cầu: cho xâu $S$, hãy xác định số cách chia Palind có thể thực hiện trên xâu $S$.

Dữ liệu: dòng duy nhất ghi xâu $S$ (không rỗng) chỉ gồm các ký tự chữ cái thường 'a'..'z'. Số lượng ký tự của $S$ không quá 16 ký tự.

Kết quả: một dòng duy nhất ghi số lượng phép chia Palind có thể thực hiện trên xâu $S$.

Giới hạn

• 50% số test tương ứng với 50% số điểm có độ dài xâu không vượt quá 10 ký tự.
• 50% số test tương ứng với 50% số điểm có độ dài xâu từ 10 đến 16 ký tự.

INPUT	OUTPUT
aab	2
a	1
banana	5

Giải thích: ví dụ 1, $S$ = "aab" có thể thực hiện được 2 phép chia Palind như sau: [aa][b] và [a][a][b].

Lời mở đầu

Bài này nếu làm tối ưu nhất thì dùng quy hoạch động. Nhưng em để ý giới hạn đề: xâu dài tối đa 16 ký tự, khá là ít. Với dữ liệu nhỏ như vậy, thầy muốn các em luyện một cách làm vét cạn rất đẹp và rất dễ nghĩ: sinh dãy nhị phân. Giải quyết được bài in ra các dãy nhị phân có chiều dài $n$ là em giải quyết được bài này. Quan trọng là phải nhìn ra được.

Bài này thầy không đăng code

Thầy muốn các em tự cài đặt theo ý tưởng bên dưới. Cuối bài có khung Chấm thử để em dán code vào chạy với test ví dụ, rồi nộp lên CLUE OJ để chấm với bộ test đầy đủ. Làm mãi không ra thì nhắn thầy, thầy sẽ gửi code trực tiếp và chỉ ra chỗ em đang vướng.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bước 1Hiểu đềBước 2Ý tưởng sinh nhị phânBước 3Minh hoạ tương tácBước 4Độ phức tạpBước 5Tự cài đặt

Bước 1Hiểu đề: "chia xâu" nghĩa là gì?

Đề bài cho mình một xâu có độ dài tối đa 16 ký tự. Mình hãy tìm một cách cắt xâu ra làm các đoạn liên tiếp sao cho sau khi cắt thì tất cả các xâu trong từng đoạn đều phải đối xứng. Nếu thoả mãn điều đó thì được xem là một cách cắt hợp lệ. Và ta hãy đếm xem có bao nhiêu cách cắt hợp lệ.

Ví dụ với xâu banana, đây là đủ 5 cách cắt hợp lệ (ô xanh là đoạn đối xứng):

Cách 1

010001

banana

Cách 2

010101

banana

Cách 3

010111

banana

Cách 4

011101

banana

Cách 5

011111

banana

Còn ví dụ một cách cắt không hợp lệ: [ban][ana] vì đoạn ban đọc ngược là nab, không đối xứng (ô đỏ):

000111

banana

✘ Không hợp lệ

Bước 2Ý tưởng: mỗi dãy nhị phân là một cách cắt

Đây là mấu chốt của bài. Em tạo ra một dãy nhị phân có chiều dài $n$ (bằng đúng độ dài xâu), mỗi bit đứng "trên đầu" một ký tự. Giả sử dãy nhị phân là 0010100, đánh số vị trí từ 1 từ trái qua phải:

0010100

1234567

abcdefg

Như vậy em sẽ hiểu rằng ta có thể cắt nó thành các đoạn [1, 2], [3], [4], [5], [6, 7].

Quy tắc cắt

Một đoạn liên tiếp các bit giống nhau được xem là một đoạn, cho tới khi gặp một bit khác thì bắt đầu đoạn mới. Nói cách khác: chỗ nào hai bit cạnh nhau khác nhau thì chỗ đó có một nhát cắt.

Rồi thì với mỗi đoạn tìm được, chỉ đơn giản là kiểm tra tính đối xứng thôi. Tất cả các đoạn đều đối xứng thì đếm thêm 1 cách.

Chạy tay với xâu aab (n = 3)

Ta tạo ra các xâu nhị phân có chiều dài 3, và chỉ tạo những dãy có bit ngoài cùng bên trái là 0 (lý do ở mục ngay dưới). Ta có 4 dãy: 000, 001, 010, 011.

Dãy nhị phân	Cách cắt	Từng đoạn có đối xứng?	Hợp lệ
000	[aab]	aab	✘
001	[aa] | [b]	aa, b	✔
010	[a] | [a] | [b]	a, a, b	✔
011	[a] | [ab]	a, ab	✘
Số cách chia hợp lệ			2

• 000: tất cả đều giống nhau nên xem như cắt được một đoạn duy nhất là aab. Xâu này không đối xứng nên không hợp lệ.
• 001: cắt ra được 2 xâu là aa và b. Cả hai đều đối xứng nên hợp lệ.
• 010: cắt ra được 3 xâu là a, a và b. Cả ba đều đối xứng nên hợp lệ.
• 011: cắt ra được 2 xâu là a và ab. Xâu a đối xứng nhưng ab thì không, nên không hợp lệ.

Vậy sau cùng chỉ có 2 cách cắt hợp lệ, đáp án là 2. Khớp với ví dụ của đề!

Vì sao bit đầu tiên luôn là 0?

Vì nhát cắt chỉ phụ thuộc vào chỗ hai bit cạnh nhau có khác nhau hay không, chứ không phụ thuộc bit đó là 0 hay 1. Nên dãy 001 và dãy "lật ngược hết" 110 cho ra cùng một cách cắt:

001

aab

✔ Hợp lệ

=

110

aab

✔ Hợp lệ

Nếu sinh cả hai thì mỗi cách cắt bị đếm 2 lần. Cố định bit đầu bằng 0 là mỗi cách cắt chỉ xuất hiện đúng 1 lần, số dãy cần xét cũng giảm còn một nửa: $2^{n-1}$.

Bước 3Minh hoạ: tự tay chạy thử mọi dãy nhị phân

Em nhập một xâu bất kỳ (chữ thường, tối đa 16 ký tự), rồi bấm Tiếp ▶ để đi qua từng dãy nhị phân, hoặc Tự chạy để xem máy thử lần lượt. Ô xanh là đoạn đối xứng, ô đỏ là đoạn không đối xứng.

Xâu S

Bước 4Có bị quá thời gian không?

Em xét qua tất cả các dãy nhị phân có chiều dài $n$ với bit đầu bằng 0: có $2^{n-1}$ dãy. Với mỗi dãy, em đi một lượt qua xâu để cắt và kiểm tra đối xứng, mất khoảng $n$ bước.

2ⁿ⁻¹ × n  =  2¹⁵ × 16  =  524 288 phép tính  (với n = 16)

Kể cả em không bỏ bit đầu, xét đủ $2^{16}$ dãy thì $16 \times 2^{16}$ cũng chỉ hơn 1 triệu phép tính. Vẫn dưới ngưỡng khoảng $10^8$ phép tính mỗi giây rất xa, nên chắc chắn không bị quá thời gian.

Bài này: ~524 nghìn

Ngưỡng 1 giây: ~100 triệu

Bước 5Tự cài đặt: các bước em cần làm

1. Sinh dãy nhị phân độ dài n. Dùng lại đúng bài "liệt kê các dãy nhị phân độ dài $n$" em đã học (sinh kế tiếp: tìm từ phải sang bit 0 đầu tiên, đổi thành 1, các bit phía sau về 0). Chỉ khác là giữ nguyên bit đầu tiên bằng 0, nên dừng khi không còn bit 0 nào từ vị trí thứ 2 trở đi.
2. Cắt xâu theo dãy bit. Đi từ trái sang phải, gom ký tự vào một xâu tạm. Gặp vị trí mà bit khác bit ngay trước nó thì đoạn đang gom đã kết thúc: kiểm tra xâu tạm có đối xứng không, rồi bắt đầu gom đoạn mới.
3. Kiểm tra và đếm. Đoạn nào không đối xứng thì dừng ngay, dãy này không hợp lệ. Đi hết xâu mà mọi đoạn đều đối xứng thì tăng biến đếm lên 1.

Em xem máy làm đúng 3 bước trên với từng ký tự nhé. Nhập một xâu ngắn (tối đa 6 ký tự) rồi bấm Tiếp: vạch đỏ là nhát cắt (chỗ hai bit cạnh nhau khác nhau), ô vàng là đoạn đang gom, xanh/đỏ là đoạn đã kiểm tra đối xứng / không đối xứng. Khi sinh dãy kế tiếp, ô viền cam là bit 0 được đổi thành 1, viền nét đứt là các bit bị đưa về 0:

Xâu S

Ví dụ nhanh:

3 lỗi hay gặp

• Quên kiểm tra đoạn cuối cùng. Khi vòng lặp chạy hết xâu, đoạn đang gom dở vẫn chưa được kiểm tra!
• Sinh cả dãy có bit đầu là 1 làm đáp án bị gấp đôi. Thử với aab mà ra 4 là bị lỗi này.
• Xâu 1 ký tự: chỉ có đúng 1 dãy là 0, đáp án phải là 1. Nhớ thử với test a.

Viết xong, em kéo xuống khung Chấm thử ở cuối bài, dán code vào và bấm ✔ Chấm với test ví dụ. Qua hết 3 test rồi thì thử thêm vài xâu tự nghĩ, so với kết quả của khung minh hoạ ở Bước 3 nhé. Ví dụ: aaaa phải ra 8, còn abcd phải ra 1.

Mở rộng: nếu xâu dài 1000 ký tự thì sao?

Khi đó $2^{999}$ dãy nhị phân thì vét cạn chịu thua, và đó là lúc cần đến quy hoạch động, cách làm tối ưu nhất của bài này. Nhưng với giới hạn 16 ký tự, cách sinh nhị phân ở trên là đủ điểm tối đa, lại giúp em luyện rất tốt kỹ năng biến bài toán thành việc duyệt mọi trường hợp. Kỹ năng này sẽ còn dùng lại ở rất nhiều bài khác.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇