Bài tập lập trình "siêu mã"

[nnvn]

Mình mới học C++ có một bài tập mình muốn nhờ các bạn cho mình ý tưởng để giải. Bài tập như sau :

Siêu mã là một loại mã có nhiều ứng dụng quan trọng trong lĩnh vực mã hóa và truyền tin. Trong bài này, ta xét bài toán đơn giản sau đây về siêu mã. Cho u và v là hai xâu kí tự khác rỗng có độ dài hữu hạn. Xâu u được gọi là xâu con của xâu v nếu u có thể nhận được từ v bằng cách xóa bớt ít nhất một kí tự trong v. Một tập X các xâu khác rỗng có độ dài hữu hạn được gọi là siêu mã nếu mọi cặp u, v bất kỳ thuộc X, u không là xâu con của v và v không là xâu con của u.
Cho trước một tập X = {x1, x2, ..., xN} gồm N xâu khác rỗng, mỗi kí tự trong xâu là 0 hoặc 1. Hãy kiểm tra xem X có là một siêu mã hay không?
Dữ liệu: vào từ file văn bản HCODE.INP có định dạng như sau:
• Dòng đầu tiên chứa số nguyên dương N (N ≤ 500);
• Dòng thứ i trong N dòng tiếp theo ghi xâu xi của tập X, độ dài của xâu xi không quá 15, với i = 1, 2, ..., N.
Kết quả: ghi ra file văn bản HCODE.OUT có định dạng như sau:
• Nếu X là siêu mã thì ghi số 1;
• Nếu X không là siêu mã thì dòng đầu tiên ghi số 0, dòng thứ hai ghi chỉ số i nhỏ nhất mà hoặc xi là xâu con của xj hoặc xj là xâu con của xi, với xi, xj thuộc X, 1 ≤ i < j ≤ N.
Ví dụ:
HCODE.INP
5
1111
100101
01011
000
0001000
HCODE.OUT
0
2

HCODE.INP
3
010
1000
11
HCODE.OUT
1

[naolmikevol]

ka ka. Lại một bài luyện gà nữa nè.

Tớ có ý kiến thế này cậu coi thử nhé. Mấu chốt là cậu so sánh 2 chuối xi bất kì thôi đúng không .

Về chuyện này tớ có nhiều ý để có thể loại bỏ đi 1 cách sớm nhất tuy nhiên tớ thấy ko ổn lắm để về lại nghĩ tiếp. Cách cơ bản (và cũng là rất chuối) là cách này.

Giả sử 2 dãy đưa vào lần lượt là x1[n] và x2[m] phần tử .

Xét trường hợp n=m:
+ Không thỏa .
Trường hợp n<m
+ Duyệt lần lượt các phần tử của n.
+ Tại phần tử thứ i, ta kiểm tra phần tử tiếp theo của x2 sao cho x2[j] =x1[i]
+ Nếu ta tìm được tất cả các phần tử thuộc x1 đều có thể tìm được phần tử tương ứng ( trái sang phải ) bên x2 thì đây là thằng cần tìm.

Về cơ bản là như thế đã.

[nhim_xi]

Up lại cho một bài toán hay!
Đầy là 1 bài toán trong đề thi OLYMPIC TIN HỌC SINH VIÊN LẦN 15, 2006.
Em cũng đang định thi O-09, nên đang xem luyện lại, pác này cùng hướng đi thì pm làm quen, trao đổi học hỏi thêm nhé. Y!M: nhimsonic_89

[Abel]

Bài này hay quá Giờ em mới bít!

[nhim_xi]

Mình mới học C++ có một bài tập mình muốn nhờ các bạn cho mình ý tưởng để giải. Bài tập như sau :

Siêu mã là một loại mã có nhiều ứng dụng quan trọng trong lĩnh vực mã hóa và truyền tin. Trong bài này, ta xét bài toán đơn giản sau đây về siêu mã. Cho u và v là hai xâu kí tự khác rỗng có độ dài hữu hạn. Xâu u được gọi là xâu con của xâu v nếu u có thể nhận được từ v bằng cách xóa bớt ít nhất một kí tự trong v. Một tập X các xâu khác rỗng có độ dài hữu hạn được gọi là siêu mã nếu mọi cặp u, v bất kỳ thuộc X, u không là xâu con của v và v không là xâu con của u.
Cho trước một tập X = {x1, x2, ..., xN} gồm N xâu khác rỗng, mỗi kí tự trong xâu là 0 hoặc 1. Hãy kiểm tra xem X có là một siêu mã hay không?
Dữ liệu: vào từ file văn bản HCODE.INP có định dạng như sau:
• Dòng đầu tiên chứa số nguyên dương N (N ≤ 500);
• Dòng thứ i trong N dòng tiếp theo ghi xâu xi của tập X, độ dài của xâu xi không quá 15, với i = 1, 2, ..., N.
Kết quả: ghi ra file văn bản HCODE.OUT có định dạng như sau:
• Nếu X là siêu mã thì ghi số 1;
• Nếu X không là siêu mã thì dòng đầu tiên ghi số 0, dòng thứ hai ghi chỉ số i nhỏ nhất mà hoặc xi là xâu con của xj hoặc xj là xâu con của xi, với xi, xj thuộc X, 1 ≤ i < j ≤ N.
Ví dụ:
HCODE.INP
5
1111
100101
01011
000
0001000
HCODE.OUT
0
2

HCODE.INP
3
010
1000
11
HCODE.OUT
1

Mình đọc tập tin trên vào biến FILE f, vào một mảng A kiểu char[15] gồm N phần tử. Đọc dữ liệu thì có thể dùng hàm fscanf hoặc fgets.
Nhưng chỉ đọc được vào 1 biến kiểu char, chưa đọc vào mảng được, báo lỗi ko thể chuyển kiểu char sang char* gì đó, bạn nào test giúp mình với.