Hỏi về thuật toán nén chuỗi

conan4582 · May 1, 2021, 1:32pm

Đề: 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

Rok_Hoang · July 7, 2016, 2:08pm

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.

minhthai · July 7, 2016, 2:09pm

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

conan4582 · July 7, 2016, 2:15pm

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)

minhthai · July 7, 2016, 2:18pm

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_Huu · July 7, 2016, 2:29pm

pascal a

Phong_Ky_Vo · July 7, 2016, 3:08pm

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

chazo1994 · July 7, 2016, 4:50pm

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