Bài 26.5. Phân tích Sự Lặp lại trong Gen Di truyền - [Độ khó: Siêu khó]

Trong lĩnh vực tin sinh học, việc phân tích chuỗi DNA để tìm kiếm các đoạn lặp lại là rất quan trọng. Các đoạn lặp lại này có thể chỉ ra các vùng chức năng, các sự kiện đột biến, hoặc các yếu tố tiến hóa. Một trong những vấn đề thú vị là tìm kiếm xâu con dài nhất mà xuất hiện ít nhất hai lần trong một chuỗi DNA, với điều kiện quan trọng là các lần xuất hiện đó không được chồng lấn lên nhau.

Ví dụ: trong chuỗi ABABAB, xâu con ABA lặp lại hai lần, nhưng chúng chồng lấn nhau (ABABAB). Xâu con AB cũng lặp lại, AB thứ nhất ở vị trí 0, AB thứ hai ở vị trí 2, chúng không chồng lấn. AB thứ ba ở vị trí 4, không chồng lấn với hai cái trước. Xâu con A ở vị trí 0 và A ở vị trí 2 cũng không chồng lấn. Nhiệm vụ của bạn là tìm độ dài của xâu con dài nhất thỏa mãn điều kiện này.

INPUT FORMAT

Một chuỗi DNA duy nhất. Chuỗi chỉ chứa các ký tự A, C, G, T (viết hoa). Độ dài chuỗi DNA N có thể lên đến 100,000 ký tự.

OUTPUT FORMAT

In ra một số nguyên duy nhất là độ dài của xâu con dài nhất thỏa mãn yêu cầu. Nếu không có xâu con nào lặp lại không chồng lấn, in 0.

Ví dụ:

Input:

ACGTACGT

Output:

4

Giải thích:

• Xâu con "ACGT" xuất hiện tại vị trí 0 và vị trí 4. Hai lần xuất hiện này không chồng lấn (kết thúc của lần xuất hiện đầu tiên là 0+4-1=3, bắt đầu của lần xuất hiện thứ hai là 4; 3 < 4). Độ dài là 4.
• Không có xâu con nào dài hơn 4 thỏa mãn điều kiện này.

Input (ví dụ khác):

AAAAA

Output:

2

Giải thích:

• Xâu con "AAA" xuất hiện tại vị trí 0 và 1, chúng chồng lấn. Cũng tại vị trí 0 và 2, chồng lấn.
• Xâu con "AA" xuất hiện tại vị trí 0, 1, 2, 3.
  • "AA" tại 0 và "AA" tại 2: không chồng lấn (kết thúc 1, bắt đầu 2). Độ dài 2.
  • "AA" tại 0 và "AA" tại 3: không chồng lấn.
• Độ dài lớn nhất mà không chồng lấn là 2.
• Nếu ta chọn "AA" tại vị trí 0 (kết thúc tại 1) và "AA" tại vị trí 2 (bắt đầu tại 2), chúng không chồng lấn. Độ dài 2.
• Nếu ta chọn "AA" tại vị trí 0 (kết thúc tại 1) và "AA" tại vị trí 1 (bắt đầu tại 1), chúng chồng lấn (vị trí 1 của "AA" đầu tiên và vị trí 1 của "AA" thứ hai là cùng một ký tự).

Input (ví dụ khác):

ABCDEFG

Output:

0

Giải thích: Không có xâu con nào lặp lại.

Input (ví dụ khác):

BANANA

Output:

2

Giải thích:

• Xâu con "ANA" xuất hiện tại vị trí 1 và 3. 1+3-1 = 3. 3 = 3, chúng chồng lấn ở ký tự thứ 3 (N).
• Xâu con "AN" xuất hiện tại vị trí 1 và 3. 1+2-1 = 2. 2 < 3. Không chồng lấn. Độ dài 2.
• "NA" xuất hiện tại vị trí 2 và 4. Không chồng lấn. Độ dài 2.
• Độ dài lớn nhất là 2.