Cho hai DFA đầy đủ trên cùng bảng chữ cái. Trên DFA tích, hãy tìm chuỗi ngắn nhất thuộc L1 ∩ L2; nếu có nhiều chuỗi cùng độ dài ngắn nhất, chọn chuỗi nhỏ nhất theo thứ tự từ điển (ký tự a<b<c<…). Dùng BFS duyệt cạnh theo thứ tự ký tự tăng dần. Nếu chuỗi rỗng thuộc giao, in -. Nếu giao rỗng, in -1.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
2 2
1 0
0 1
0
1 1
2 2
0 1
1 0
0
1 1
Output:
ab
Hai khối DFA liên tiếp, mỗi khối theo định dạng: Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).
Hai DFA có cùng kích thước bảng chữ cái k.1 ≤ n1,n2 ≤ 1000, 1 ≤ k ≤ 26.
In chuỗi ngắn nhất (nhỏ nhất theo từ điển) thuộc L1 ∩ L2; - nếu là chuỗi rỗng; -1 nếu giao rỗng.
Ví dụ:
Đầu vào:
2 2
1 0
0 1
0
1 1
2 2
0 1
1 0
0
1 1
Đầu ra:
ab
Giải thích:
Đang tải editor...