Một Số Thuật Toán Tìm Xâu Con đối Xứng Dài Nhất

1tailieu Danh mục:

• Đăng nhập
• Khoa học xã hội
• Đề thi lớp 5
• Tuyển sinh lớp 10
• Trung học phổ thông
• Luyện thi Đại học - Cao đẳng
• Sáng kiến kinh nghiệm
• Luận văn
  • Kinh tế thương mại
  • Công nghệ thông tin
  • Công nghệ - Môi trường
  • Y khoa - Dược
  • Khoa học xã hội
  • Khoa học tự nhiên
  • Nông - Lâm - Ngư
  • Báo cáo khoa học
  • Thạc sĩ - Cao học
  • Tiến sĩ
  • Kinh tế - Quản lý
  • Lý luận chính trị
  • Kỹ thuật
  • Kinh tế
  • Khoa học xã hội
  • Khoa học tự nhiên
  • Công nghệ thông tin
  • Kỹ thuật
  • Nông - Lâm - Ngư
  • Kiến trúc - Xây dựng
  • Luật
  • Sư phạm
  • Y dược - Sinh học
  • Dịch vụ - Du lịch
  • Bất động sản
  • Tài chính - Ngân hàng
  • Quản trị kinh doanh
  • Kế toán
  • Kiểm toán
  • Xuất nhập khẩu
  • Chứng khoán
  • Tài chính thuế
  • Marketing
  • Bảo hiểm
  • Định giá - Đấu thầu
  • Toán học
  • Vật lý
  • Hóa học
  • Sinh học
  • Địa lý - Địa chất
  • Triết học Mác - Lênin
  • Đường lối cách mạng
  • Kinh tế chính trị
  • Chủ nghĩa xã hội khoa học
  • Tư tưởng Hồ Chí Minh
  • Quản trị mạng
  • Lập trình
  • Đồ họa
  • Web
  • Hệ thống thông tin
  • Thương mại điện tử
  • Giao thông - Vận tải
  • Điện - Điện tử
  • Viễn thông
  • Cơ khí - Vật liệu
  • Kiến trúc - Xây dựng
  • Lập trình di động
  • Lâm nghiệp
  • Nông học
  • Chăn nuôi
  • Thú y
  • Thủy sản
  • Công nghệ thực phẩm
  • Cao su - Cà phê - Hồ tiêu
  • Quan hệ quốc tế
  • Giáo dục học
  • Đông phương học
  • Việt Nam học
  • Văn hóa - Lịch sử
  • Xã hội học
  • Báo chí
  • Tâm lý học
  • Văn học - Ngôn ngữ học

Từ khoá:

• skkn
• đề thi thpt
• luận văn
• khoá luận

1tailieu

Thư viện tài liệu

1. Trang chủ
2. tài liệu

Đăng nhập

Một số thuật toán tìm xâu con đối xứng dài nhất

• 12 trang
• file: .pdf

Chia sẻ từ tailieu

đang tải dữ liệu....

Xem thêm trang

Tài liệu bị giới hạn, để xem hết nội dung vui lòng tải về máy tính.

Tải xuống - 12 trang

Nội dung text: Một số thuật toán tìm xâu con đối xứng dài nhất

tailieuonthi MỘT SỐ THUẬT TOÁN TÌM XÂU CON ĐỐI XỨNG DÀI NHẤT I. Mở đầu Xâ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 đều giố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ũng có 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 đền cần quan 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ác phâ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à đối xứng. Dữ liệu vào: PALIN.INP Gồm một dòng chứa duy nhất một xâu S Dữ liệu ra: PALIN.OUT Ghi độ dài xâu con dài nhất của S là đối xứng. Ví dụ: PALIN.INP PALIN.OUT abccbghjkaaaaaaaaaakfwg 12 II. 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ó đối xứ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ứng và trả về giá trị False trong trường hợp ngược lại. Function IsPalin(i,j:longint):boolean; var k:longint; begin 1 tailieuonthi for k:=0 to (j-i+1)div 2 do if 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ại kế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úc của xâu con đối xứng dài nhất. procedure process; var i,j:longint; begin LongPalin:=1; cuoi:=1; cuoi:=1; for i:=1 to n-1 do for j:=n downto i+1 do if IsPalin(i,j) then if j-i+1>longPalin then begin Longpalin:=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]+2 Nế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; begin fillchar(L,sizeof(L),0); for i:=1 to n do L[i,i]:=1; 2 tailieuonthi for i:=n-1 downto 1 do for j:=i+1 to n do if s[i]=s[j] then L[i,j]:=L[i+1,j-1]+2 else L[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 1 chỗ 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ài nhấ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áo P:array[0..2*n] of longint. Chương trình: procedure xuly; var i,dau,cuoi:longint; begin n:=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ất e1:=1;//e1: vị trí kết thúc của xâu con đối xứng dài nhất s1:=1;// s1: vị trí bắt đầu của xâu con đối xứng dài nhất for i:=2 to m-2 do begin if (i mod 2=0) then begin dau:=i div 2; cuoi:=dau+1; end else begin 3 tailieuonthi P[i]:=1; dau:=(i div 2) ; cuoi:=dau+2; end; while (dau>=1) and (cuoimax then begin max:=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âu S, 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=0103016103010 4 tailieuonthi Nhận thấy, độ dài xâu con đối xứng dài nhất là “abaaba”, tại vị trí P6=6 Xé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ạn T[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ếp P[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àng là sai, vì trong trường hợp này, khi mở rộng quanh trung tâm T15 ta được xâu con đối xứng là “a#b#c#b#a”, nghĩa là P[15]=5, tại sao? 5 tailieuonthi 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ứng nhau 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ại R ; // R là vị trí đang xét về bên phải trung tâm hiện tại C Res 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 do Tính i’ 2*C-i; // I’ là vị trí đối xứng về bên trái trung tâm C; Nếu iR thì: C i; R i+P[i]; Nếu res0) 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à i begin C:=i; R:=i+P[i]; end; if res