30/09/2018, 22:02

Cho em hỏi về thuật toán nén chuỗi

Đề: Cho 1 chuỗi, nén chuỗi tối ưu:
vd: aabbbcdededereaabbc
-> 2a3bcdededere2a2bc
-> 2a3bc3(de)re2a2bc
Em có ý tưởng là cho duyệt theo từng dãy con nhưng code mãi vẫn ko return kq đúng
các cao nhân giúp em vs

Minh Hoàng viết 00:07 ngày 01/10/2018

gần giống thuật toán nén LZW ý tưởng thuật toán của bạn chưa rõ ràng lắm, nếu nén như vậy sẽ bị xung đột mất.

mt viết 00:03 ngày 01/10/2018

Bạn làm dc đến độ phức tạp cỡ nào rồi

Quốc Hùng viết 00:11 ngày 01/10/2018

ý tưởng thuật toán của bạn chưa rõ ràng lắm, nếu nén như vậy sẽ bị xung đột mất.

for i:= 1 to length(s) do begin
                if s[i] = s[i+1] then inc(count) else begin
                        if count = 1 then z:=z+s[i]
                        else z:= z+inttostr(count)+s[i];
                        count:=1;
                end;
        end;

        s:=z;

        for len:=2 to length(s) do begin
                for i:= 1 to length(s) do begin
                        if (copy(s,i,len) = copy(s,i+len+1,len)) then inc(count) else begin
                                if count <> 1 then t:= t+'('+inttostr(count)+')'+copy(s,i,len);
                                count:= 1;
                        end;
                end;
        end;

nó sinh ra tùm lum , @minhthai chắc là O(n^2)

mt viết 00:14 ngày 01/10/2018

mình chưa code thử nữa nhưg cách của mình cũng n^2, dùng mảng fail của KMP

Mai Hữu viết 00:17 ngày 01/10/2018

pascal a

Tao Không Ngu. viết 00:05 ngày 01/10/2018

This post was flagged by the community and is temporarily hidden.

chazo1994 viết 00:10 ngày 01/10/2018

dùng thử thuật toán lempel ziv đi bạn

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger