Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Khớp tham lam và khớp lười

    Trong các động cơ regex, .*X (tham lam) và .*?X (lười) có thể khớp các đoạn khác nhau của cùng một xâu. Xét mẫu dạng R∗LR^{*}LR∗L trong đó RRR là một lớp kí tự lặp (một chữ cái cố định, hoặc kí hiệu đặc biệt chỉ bất kì kí tự nào — như dấu .) còn LLL là một xâu hậu tố cố định (không rỗng). Cho một văn bản TTT, hãy tìm vị trí bắt đầu khớp trái nhất iii (0-indexed) sao cho tồn tại j≥ij \ge ij≥i để T[i..j)T[i..j)T[i..j) toàn bộ thoả RRR và T[j..j+∣L∣)=LT[j..j+|L|) = LT[j..j+∣L∣)=L. Trong số các jjj hợp lệ ứng với iii trái nhất đó, gọi k=j−ik=j-ik=j−i là độ dài phần lặp đã khớp:

    • Chế độ lười (lazy): chọn kkk nhỏ nhất.
    • Chế độ tham lam (greedy): chọn kkk lớn nhất.

    Nếu không có iii nào thoả mãn trên toàn văn bản, in NO MATCH.

    • Định dạng đầu vào:

      Dòng 1: hai token cách nhau bởi khoảng trắng — token thứ nhất mô tả RRR: hoặc một chữ cái thường (chỉ kí tự đó được lặp), hoặc từ khoá ANY (mọi kí tự đều thoả, tương đương . trong regex); token thứ hai là xâu hậu tố LLL (chữ cái thường, độ dài ≥1\ge 1≥1). Dòng 2: văn bản TTT (chữ cái thường, xâu rỗng biểu diễn bằng @).

    • Định dạng đầu ra:

      Nếu có khớp: một dòng ba số nguyên i lazy greedy cách nhau khoảng trắng. Nếu không: dòng NO MATCH.

      Ví dụ: ANY ab và văn bản xxabab cho kết quả 0 2 4 (khớp trái nhất tại i=0i=0i=0; lười dừng ở độ dài lặp 222, tham lam ở độ dài lặp 444).

    Ví dụ:

    Đầu vào:

    a b
aaab

    Đầu ra:

    0 3 3

    Đầu vào:

    ANY ab
xxabab

    Đầu ra:

    0 2 4

    Đang tải editor...