ĐỀ RA

Bài 2. (5 điểm) ĐOẠN MAX
            Cho chuỗi kí tự S gồm toàn các chữ cái in hoa (A…Z) với độ dài không vượt quá 10⁴.
Yêu cầu: Hãy tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đầu tiên trong chuỗi S.
Dữ liệu: Vào từ văn bản DOANMAX.INP:  
- Gồm một dòng duy nhất chứa chuỗi S.
Kết quả: Ghi ra file văn bản DOANMAX.OUT
- Chỉ một dòng duy nhất chứa số nguyên P và L tương ứng là vị trí và chiều dài của đoạn con dài nhất tìm được.
Ví dụ:

DOANMAX.INP	DOANMAX.OUT
ABABCDAC	3 4

Lưu ý: Có 80% số test có độ dài xâu S không vượt quá 255.
Giải thích test ví dụ: Đoạn con dài nhất tìm được là ABCD có vị trí 3 và độ dài 4

 

GIẢI

Cách 1

# Đọc dữ liệu từ file input
f = open('DOANMAX.INP', 'r')
s = f.readline().strip()
f.close()

# Tìm đoạn con dài nhất không có kí tự nào xuất hiện nhiều hơn 1 lần
max_len = 0
max_start = 0

for i in range(len(s)):
    chars = set()
    j = i
    while j < len(s) and s[j] not in chars:
        chars.add(s[j])
        j += 1
    if j-i > max_len:
        max_len = j-i
        max_start = i

# Ghi kết quả vào file output
f = open('DOANMAX.OUT', 'w')
f.write(str(max_start+1) + ' ' + str(max_len))
f.close()

Giải thích:

• Đầu tiên, chúng ta đọc dữ liệu từ file input bằng cách mở file và đọc dòng đầu tiên bằng hàm readline().
• Tiếp theo, chúng ta sử dụng vòng lặp để duyệt qua từng vị trí trong chuỗi s. Tại mỗi vị trí đó, chúng ta sử dụng một tập hợp chars để lưu các kí tự đã xuất hiện. Chúng ta duyệt từ vị trí hiện tại đến cuối chuỗi hoặc tới khi gặp một kí tự đã xuất hiện trước đó. Nếu đoạn con này dài hơn đoạn con trước đó, chúng ta cập nhật lại max_len và max_start.
• Cuối cùng, chúng ta ghi kết quả vào file output bằng cách mở file và sử dụng hàm write() để ghi chuỗi kết quả. Lưu ý rằng vì vị trí đếm từ 1 nên chúng ta cộng thêm 1 vào max_start trước khi ghi kết quả.

Cách 2

# Đọc input từ file
with open("DOANMAX.INP", "r") as f:
    s = f.read().strip()

n = len(s)
ans_start = 0
ans_len = 0

# Tìm đoạn con dài nhất không có kí tự xuất hiện nhiều hơn 1 lần
for i in range(n):
    # Khởi tạo một mảng đánh dấu các kí tự đã xuất hiện
    appeared = [False] * 26
    for j in range(i, n):
        # Nếu kí tự j đã xuất hiện trước đó thì thoát vòng lặp
        if appeared[ord(s[j]) - ord('A')]:
            break
        # Đánh dấu kí tự j đã xuất hiện
        appeared[ord(s[j]) - ord('A')] = True
        # Nếu đoạn con hiện tại dài hơn đoạn con tìm được trước đó thì cập nhật lại kết quả
        if j - i + 1 > ans_len:
            ans_start = i
            ans_len = j - i + 1

# Ghi output vào file
with open("DOANMAX.OUT", "w") as f:
    f.write(str(ans_start + 1) + " " + str(ans_len))

Giải thích:

• Đầu tiên, ta đọc input từ file và lưu vào biến s.
• Tiếp theo, ta duyệt từng vị trí trong chuỗi s và tìm đoạn con dài nhất không có kí tự xuất hiện nhiều hơn 1 lần bắt đầu từ vị trí đó. Để làm được điều này, ta sử dụng một mảng appeared để đánh dấu các kí tự đã xuất hiện trong đoạn con hiện tại. Nếu một kí tự đã xuất hiện trước đó thì ta thoát khỏi vòng lặp và tiếp tục duyệt đến vị trí tiếp theo. Nếu đoạn con hiện tại dài hơn đoạn con tìm được trước đó thì ta cập nhật kết quả.
• Cuối cùng, ta ghi output vào file với định dạng là vị trí đầu tiên của đoạn con và chiều dài của đoạn con dài nhất tìm được. Lưu ý là vị trí đầu tiên trong chuỗi là 1, không phải 0.
• if appeared[ord(s[j]) - ord('A')]  Dòng lệnh này kiểm tra xem ký tự tại vị trí j trong chuỗi s đã xuất hiện trước đó chưa. Biến appeared lưu trữ thông tin về sự xuất hiện của các ký tự. Nếu ký tự đã xuất hiện trước đó, biểu thức trong điều kiện sẽ trả về giá trị True, ngược lại sẽ trả về giá trị False. Để có thể kiểm tra được tất cả các ký tự trong chuỗi s, ta sử dụng hàm ord để chuyển đổi ký tự sang mã ASCII, sau đó trừ đi giá trị mã ASCII của ký tự 'A' để thu được một số nguyên nhỏ hơn hoặc bằng 25 (vì có tổng cộng 26 chữ cái trong bảng chữ cái tiếng Anh).

 

 Cách 3

Trong cách này: Để giải quyết bài toán này, chúng ta có thể sử dụng một vòng lặp để duyệt qua từng vị trí trong chuỗi. Tại mỗi vị trí, chúng ta sẽ sử dụng một tập hợp để lưu trữ các kí tự đã xuất hiện và kiểm tra xem đoạn con hiện tại có dài hơn đoạn con dài nhất đã tìm thấy trước đó hay không. Nếu có, chúng ta sẽ cập nhật đoạn con dài nhất và vị trí bắt đầu của nó.

# Đọc chuỗi S từ file DOANMAX.INP
with open('DOANMAX.INP', 'r') as f:
    s = f.readline().strip()

# Khởi tạo biến lưu đoạn con dài nhất và vị trí bắt đầu của nó
max_len = 0
start_pos = 0

# Khởi tạo tập hợp để lưu trữ các kí tự đã xuất hiện
char_set = set()

# Duyệt qua từng vị trí trong chuỗi
for i in range(len(s)):
    # Nếu kí tự hiện tại đã xuất hiện trong đoạn con trước đó
    # hoặc đã xuất hiện trong tập hợp
    if s[i] in char_set:
        # Xóa hết các kí tự trong tập hợp
        char_set.clear()
        # Đặt lại vị trí bắt đầu của đoạn con
        start_pos = i
    # Thêm kí tự hiện tại vào tập hợp
    char_set.add(s[i])
    # Tính độ dài của đoạn con hiện tại
    curr_len = len(char_set)
    # Nếu đoạn con hiện tại dài hơn đoạn con dài nhất đã tìm thấy trước đó
    if curr_len > max_len:
        # Cập nhật đoạn con dài nhất và vị trí bắt đầu của nó
        max_len = curr_len
        start_pos = i - curr_len + 1

# Ghi kết quả vào file DOANMAX.OUT
with open('DOANMAX.OUT', 'w') as f:
    f.write(str(start_pos) + ' ' + str(max_len))

Sử dụng cách làm trên, chúng ta có thể tìm được đoạn con các kí tự liên tiếp dài nhất trong chuỗi S mà không có kí tự nào xuất hiện nhiều hơn một lần và ghi kết quả vào file DOANMAX.OUT.

CÁC TEST

Đã thêm các test cuối bài viết, thầy cô và các bạn tải về chạy thử nhé! Trong file tải về đã có thêm các file mẫu bằng code pascal.