Thuật Toán Manacher Xâu đối Xứng Dài Nhất - Tài Liệu Text - 123doc

Tải bản đầy đủ (.docx) (8 trang)

1. Trang chủ
>>
2. Trung học cơ sở - phổ thông
>>
3. Lớp 9

Thuật toán Manacher Xâu đối xứng dài nhất

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (96.38 KB, 8 trang )

MỘT SỐ THUẬT TOÁN TÌM XÂU CON ĐỐI XỨNG DÀI NHẤTI. Mở đầuXâu đối xứng (xâu Palindrome) là xâu đọc từ trái sang phải hay đọc từ phải qua trái đềugiống nhau, ví dụ: xâu aba, aaa, abccba… Trên thực tế, chúng ta hay gặp các bài toán cóliên quan đến xâu đối xứng ở các mức độ phức tạp khác nhau. Để giải quyết chúng cũngcó một số thuật toán được áp dụng, Tuy nhiên, lựa chọn thuật toán nào là một vấn đề cầnquan tâm.Trong bài viết này, tôi xin trình bày một số thuật toán về tìm xâu con đối xứng dài nhất,đặc biệt là thuật toán tìm xâu con đối xứng dài nhất trong thời gian tuyến tính với cácphân tích cụ thể về độ phức tạp tính toán trong mỗi thuật toán. Mục đích, để chúng ta cócái nhìn hệ thống và đưa ra cách làm tối ưu trong các bài toán cụ thể.Chúng ta cùng xem lại một bài toán quen thuộc trong tin học như sau:Bài toán: Cho một xâu S, tìm xâu con (một dãy các ký tự liên tiếp) dài nhất của S là đốixứng.Dữ liệu vào: PALIN.INPGồm một dòng chứa duy nhất một xâu SDữ liệu ra: PALIN.OUTGhi độ dài xâu con dài nhất của S là đối xứng.Ví dụ:PALIN.INPPALIN.OUTabccbghjkaaaaaaaaaakfwg12II. Nội dungĐặt n=length(S)1.Thuật toán duyệt toàn bộ (thời gian O(n3), bộ nhớ O(1))Rõ ràng xâu S có n(n-1)/2 xâu con, với mỗi xâu con chúng ta lại kiểm tra xem nó có đốixứng không. Độ phức tạp của thuật toán là O(n3).Dưới đây trình bày hàm IsPalin(i,j:longint) trả về giá trị True nếu đoạn S[i..j] là đối xứngvà trả về giá trị False trong trường hợp ngược lại.Function IsPalin(i,j:longint):boolean;var k:longint;beginfor k:=0 to (j-i+1)div 2 doif s[i+k]s[j-k] then exit(False);Exit(True);end;Thủ tục Process xét mọi xâu con của S xem nó có đối xứng không, nếu có thì cập nhật lạikết quả longPalin: độ dài xâu con đối xứng dài nhất, dau, cuoi: vị trí bắt đầu và kết thúccủa xâu con đối xứng dài nhất.procedure process;var i,j:longint;beginLongPalin:=1;cuoi:=1;cuoi:=1;for i:=1 to n-1 dofor j:=n downto i+1 doif IsPalin(i,j) thenif j-i+1>longPalin thenbeginLongpalin:=j-i+1;dau:=i;cuoi:=j;end;end;2. Thuật toán quy hoạch động (thời gian O(n2), bộ nhớ O(n2))Gọi L[i,j] là độ dài xâu con lớn nhất của đoạn từ s[i..j]- Khởi tạo: L[i,j]=0 với mọi ij, L[i,i]=1.- Công thức:Nếu s[i]=s[j] thì L[i,j]=L[i+1,j-1]+2Nếu s[i]s[j] thì L[i,j]=max(L[i,j-1], L[i+1,j])- Đáp số: L[1,n]Chương trình:procedure optimize;var i,j:longint;beginfillchar(L,sizeof(L),0);for i:=1 to n do L[i,i]:=1;for i:=n-1 downto 1 dofor j:=i+1 to n doif s[i]=s[j] then L[i,j]:=L[i+1,j-1]+2elseL[i,j]:=max(L[i+1,j],L[i,j-1]);end;3. Thuật toán duyệt trung tâm (thời gian O(n2), bộ nhớ O(n))Dễ dàng nhận thấy vị trí trung tâm của một xâu con đối xứng chỉ có thể là 1 ký tự hoặc 1chỗ trống. Như vậy, xâu S có 2n+1 trung tâm, với mỗi trung tâm đó, ta tìm xâu con dàinhất là đối xứng bằng cách xuất phát từ mỗi trung tâm, đồng thời phát triển đồng thời vềbên trái và bên phải cho đến khi tìm được xâu con đối xứng dài nhất tại trung tâm đó. Độphức tạp thuật toán là O(n2).Gọi P[i] là độ dài xâu con đối xứng dài nhất nhận vị trí i làm trung tâm, khai báoP:array[0..2*n] of longint.Chương trình:procedure xuly;var i,dau,cuoi:longint;beginn:=length(s);m:=2*n;fillchar(P,sizeof(P),0);P[1]:=1; P[m-1]:=1;max:=1;//max: độ dài xâu con đối xứng dài nhấte1:=1;//e1: vị trí kết thúc của xâu con đối xứng dài nhấts1:=1;// s1: vị trí bắt đầu của xâu con đối xứng dài nhấtfor i:=2 to m-2 dobeginif (i mod 2=0) thenbegindau:=i div 2;cuoi:=dau+1;endelsebeginP[i]:=1;dau:=(i div 2) ;cuoi:=dau+2;end;while (dau>=1) and (cuoimax thenbeginmax:=P[i];e1:=cuoi-1;s1:=dau+1;end;end;end;4. Thuật toán Manacher (thời gian O(n), bộ nhớ O(n))Có cách nào tính mảng P (ở thuật toán duyệt trung tâm) nhanh hơn không?Xét xâu S chứa nhiều xâu đối xứng chồng chéo, ví dụ: “aaaaaaaaa” và“cabcbabcbabcba”. Thực tế, ta có thể tận dụng được ưu điểm của tính đối xứng này vàtránh được các tính toán không cần thiết. Cụ thể ta làm như sau:Đầu tiên, ta thay xâu S bằng xâu T bằng cách thêm ký tự “#” vào các chỗ trống trên xâuS, ví dụ: S = “abaaba” thì T = “#a#b#a#a#b#a#”. Để tìm xâu con đối xứng dài nhất của S,ta cần mở rộng mỗi Ti về hai phía 1 khoảng d dài nhất sao cho Ti-d ..Ti+d là đối xứng. dđược gọi là bán kính của xâu con đối xứng nhận Ti làm trung tâm.Gọi P[i] là độ dài xâu con đối xứng dài nhất nhận Ti làm trung tâm, đáp số của bài toán làmax(P[i]), i=0..2*n. Với ví dụ trên, mảng P tương ứng là:T=#a#b#a#a#b#a#P=0103016103010Nhận thấy, độ dài xâu con đối xứng dài nhất là “abaaba”, tại vị trí P6=6Xét ví dụ khác, S= “babcbabcbaccba”, giả sử chúng ta đang ở trạng thái sau:C là vị trí trung tâm, L và R là vị trí mở rộng tối đa quanh trung tâm C, nghĩa là đoạnT[L..R] đối xứng có tâm là TC. Ta đã tính được mảng P như trên, làm thế nào để tính tiếpP[i] một cách hiệu quả?Với i=13, i’ là vị trí đối xứng của i qua tâm C, P[ i' ] = P[ 9 ] = 1. Rõ ràng P[i]=1 do tínhđối xứng của xâu. Tương tự, ta tính được P[ 12 ] = P[ 10 ] = 0, P[ 13 ] = P[9 ] = 1, P[ 14 ]= P[ 8 ] = 0.Tiếp theo, với i=15, theo tính chất đối xứng thì P[15]=P[7]=7 còn đúng không? Rõ rànglà sai, vì trong trường hợp này, khi mở rộng quanh trung tâm T15 ta được xâu con đốixứng là “a#b#c#b#a”, nghĩa là P[15]=5, tại sao?Trên hình vẽ 2 đường thẳng biểu diễn cho 2 xâu con đối xứng dài nhât quanh trung tâm i’(đường bên trên) và xâu con đối xứng dài nhất quanh trung tâm i, mà i và i’ đối xứngnhau qua tâm C, đường xanh nét liền thể hiện tính đối xứng quanh tâm C, đường xanh nétđứt thể hiện tính đối xứng đi xuyên qua tâm C, đường nét liền màu đỏ thể hiện ta có thểmở rộng tối đa về 2 phía thỏa mãn tính đối xứng của xâu con.Ta có: P[i’]=7, và P[i]≥5 (do tính đối xứng), trong khi vị trí đang xét là R=20, muốn tínhđược P[i] ta phải mở rộng sang phải của R, nghĩa là phải đi so sánh T[21] và T[9], màT[21]≠T[9] nên P[i]=5. Từ đó, ta có một phần thuật toán như sau:if P[ i' ] ≤ R – i,then P[ i ] ← P[ i' ]else P[ i ] ≥ P[ i' ] (khi đó ta có thể mở rộng về bên phải R để tìm P[i]).Thuật toán Manacher tìm xâu con đối xứng dài nhất của xâu S:- B1: Tính T là mở rộng của xâu S bằng cách thêm ký tự ‘#’ vào các chỗ trống- B2: Đặt n length(T)C:=1; // C là vị trí trung tâm hiện tạiR:=1; // R là vị trí đang xét về bên phải trung tâm hiện tại CRes := 0; // Res là độ dài xâu con đối xứng dài nhất của xâu S- B3: For i:=2 to n doTính i’:=2*C-i; // I’ là vị trí đối xứng về bên trái trung tâm C;Nếu i // mở rộng bán kính đối xứng quanh trung tâm iwhile (T[i-1-P[i]]=T[i+1+P[i]]) do P[i] P[i]+1;// nếu mở rộng thành công thì đặt lại trung tâm mới là I, bán kính mở rộng về bên phải R= i+P[i]Nếu i+P[i]>R thì: C :=i; R:=i+P[i];Nếu res < P[i] thì Res  P[i]; // cập nhật lại kết quảChương trình:// T là xâu mở rộng của ST:='#';for i:=1 to n dobeginT:=T+s[i]+'#';end;n:=length(T);C:=1; // C là vị trí trung tâm hiện tạiR:=1; // R là vị trí đang xét về bên phải trung tâm Cres:=0; // res: Độ dài xâu con đối xứng dài nhấtP[1]:=1;for i:=2 to n dobegini1:=2*C-i; // i1 là vị trí đối xứng về bên trái trung tâm Cif (i1>0) and (R>i) then P[i]:=min(R-i, P[i1])else P[i]:=0;while ((i-P[i]-1)>0) and ((i+P[i]+1)R then // nếu mở rộng thành công thì đặt lại trung tâm mới là ibeginC:=i;R:=i+P[i];end;if res 4. vnoi.infoLê Thị Hải HằngTài liệu liên quanNghiên cứu tính toán lưới và thử nghiệm một số thuật toán lý thuyết đồ thịNghiên cứu tính toán lưới và thực nghiệm trên một số thuật toán lý thuyết đồthịNghiên cứu tính toán lưới thử nghiệm một số thuật toán lí thuyết đồ thịMỘT SỐ THUẬT TOÁN PHÂN HẠNG ẢNH PHỔ BIẾN VÀ ÁP DỤNGTRONG HỆ THỐNG TÌM KIẾM ẢNH LỚP TRÊN THỬ NGHIỆMMỘT SỐ THUẬT TOÁN PHÂN HẠNG ẢNH PHỔ BIẾN VÀ ÁP DỤNGTRONG HỆ THỐNG TÌM KIẾM ẢNH LỚP TRÊN THỬ NGHIỆMBÁO CÁO TỐT NGHIỆP: TÌM HIỂU VÀ ĐÁNH GIÁ MỘT SỐ THUẬTTOÁN TÌM KIẾM TRUYỀN THỐNG ỨNG DỤNG TRONG TIN HỌC pdfMột số thuật toán tìm đường đi ngắn nhất và xây dựng ứng dụng GAMEPIKACHUtiểu luận một số thuật toán cặp ghép trên đồ thị hai phíanghiên cứu và thử nghiệm một số thuật toán phát hiện các đồ thị con thườngxuyênMột số thuật toán tìm chuỗi và xây dựng chương trình minh họa thuật toánboyer moore

Tài liệu liên quan

• Thuật Toán Và Thuật Giải
  • 4
  • 337
  • 0
• Thuật Toán Và Thuật Giải part 1
  • 5
  • 362
  • 0
• Một số thuật toán nâng cao bồi dưỡng hsg pascal thpt
  • 219
  • 3
  • 12
• Báo cáo "Advanced Elgamal thuật toán mật mã khoá bất đối xứng tương lai " pptx
  • 5
  • 509
  • 3
• Báo cáo đồ án nghiên cứu, cài đặt thuật toán giải bài toán lập hành trình người đưa thư và ứng dụng
  • 38
  • 1
  • 0
• Đồ án tốt nghiệp đại học “nghiên cứu, cài đặt thuật toán giải bài toán lập hành trình người đưa thư và ứng dụng”
  • 92
  • 781
  • 0
• tập hút toàn cục đối với một số lớp phương trình parabolic suy biến
  • 122
  • 528
  • 2
• tổng hợp kiến thức các bài toán hình học 7 có hướng dẫn
  • 122
  • 921
  • 0
• Chg 5 Khuếch đại thuật toán unicode
  • 35
  • 301
  • 0
• Cải tiến thuật toán biển đổi ảnh FIBONACCI - HAAR bằng phương pháp xác suất kết hợp biến đổi Lifting
  • 7
  • 320
  • 0

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(23.12 KB - 8 trang) - Thuật toán Manacher Xâu đối xứng dài nhất Tải bản đầy đủ ngay ×