Cho n xâu kí tự mỗi xâu gồm nhiều đoạn kí tự(từ a->z) cách nhau ít nhất 1 dấu cách(mã ASCII là 13) Đoạn lặp là đoạn có số kí tự được lặp lại nhiều lần. Input: -Dòng đầu nhập n là số xâu kí tự. -n dòng sau mỗi dòng nhập 1 xâu kí tự. Output: -Hãy tìm đoạn lặp liên tục dài nhất của từng xâu. VD: Input 2 aa sa la cnv a aa bb cc de(đoạn dài nhất là "aa bb cc de" mỗi đoạn 2 kí tự) abc def ghi a b c d e aa bb cc a a a a (đoạn dài nhất là "a b c d e" mỗi đoạn 1 kí tự) Output 4 5 Dữ liệu nhập từ bàn phím Mình ko nhớ rõ đề cho lắm,mà cái đề cũng gần gần như vậy(Bài này mình làm 90' mới ra)
Xét xâu thứ K (1<=K<=N) gọi F[i,j] là độ dài đoạn lặp trong khoảng [i,j] với i là đoạn thứ i, j là đoạn thứ j. Khởi tạo F[i,j]=0 hết,F[i,i]=1; M là số đoạn của xâu đang xét. Free=true nếu chưa xét i, Free=false nếu đã xét. Thế thì Mã: Max := 0; For(i=1;i<=m-1;i++) if (i là đoạn lặp && i chưa xét) {Free[i]=false; j = i+1; while (j <=m) { if (độ dài j!= độ dài j-1) break; if (j ko phải đoạn lặp) break; if (độ dài j != độ dài i) break; Free[j]=false; F[i,j] = F[i,j-1]+1; if (F[i,j]>max) max = F[i,j]; j++; } } xong rồi in ra max, rồi lại làm lại với các xâu khác theo kiểu làm multi-test thôi cách làm này là trực quan nhất, độ phức tạp tới O(n^2), có thể sẽ có cách hay hơn
Bài này khó khăn ko phải nằm ở thuật toán mà vấn đề nằm ở chỗ nhập dữ liệu(Cái này mới chết người nè) -Dòng đầu nhập n là số xâu kí tự. -n dòng sau mỗi dòng nhập 1 xâu kí tự.
thì dùng một vòng lặp while rồi mỗi lần đọc vào là xử lí luôn, in ra luôn, rồi xuống dòng lại đọc, lại xử lí, lại in kết quả thôi bác có hay làm trên các trang online judge ko, cái này là một kiểu multi-test thôi mà mình thì thấy bài này hơi ngại đoạn xử lý xâu thôi
Thanks nhiều nha hôm bữa co s nghe ông thầy nói về online judge nhưng ko biết tìm ở đâu. Sẵn đây cũng xin hỏi thêm là khi nộp bài thì file mã nguồn,file Input,Output đặt tên như thế nào?
input, output ko cần phải ghi đâu file mã nguồn cũng ko cần thiết phải đúng tên chỉ cần gửi đúng mã bài là được rồi
Bạn ơi cho mình hỏi thêm mình gửi 3 bài cả 3 bài đều Accepted nhưng có 2 bài 100 điểm còn bài kia 0 điểm là sao? Mã: Congratulations! You have solved problem NKMSG. Your program in C++ from 2008-12-13 15:29:47 ran for 0.00 seconds and used 0 KB of memory
Nhiều bài mình cũng bị thế, có thể là do dùng quá bộ nhớ bài đấy cho phép(để mai mình hỏi lại xem, nhưng mấy bài mình được chấp nhận mà cũng 0 hết đều bị quá bộ nhớ cả nên chắc là đúng) btw, phải 100 điểm mới gọi là làm trọn vẹn cơ bài này nói chung tư tưởng là DFS rồi đánh dấu những thằng nào có thể làm "con" thằng khác, rồi cuối cùng xuất ra những thằng được xác định là "bố". Bài này mình chưa chấm bao giờ, nhưng thằng bạn mình làm theo cách này AC rồi
