Chào mừng các bạn
-((`(`vŽ)--*** MasterSpy *** --(`vŽ)`))- - Thuật toán - Cấu trúc dữ liệu So khớp chuỗi với các ký tự wildcard
ღLONELYღ
  Home
  => Cách tạo một trang web cho riêng mình !
  => Một số địa chỉ trang web hay dành cho bạn, ....cho tôi !
  => 5 bước cơ bản để diệt tận gốc Spyware
  => 10 điều “lính mới” nên biết
  => 10 bước để lập kế hoạch cho nghề nghiệp tương lai của bạn
  => 15 LỜI KHUYÊN HỌC TIẾNG ANH
  => 21 kho lưu dữ liệu miễn phí trên Internet
  => PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ
  => 50 cuốn sách văn học cần đọc
  => Những bài học từ Adam Khoo
  => Dùng Admodify.net để quản trị và phục hồi Exchange 2003
  => Cuộc đời của Albert Einstein
  => Cảnh giác với hacker và keylogger!
  => Phần mềm miễn phí giúp bảo vệ computer khi online
  => Học thi - cần ăn uống hợp lý
  => Hacker “oánh” mỗi PC chỉ mất 39 giây
  => Xác định nguyên nhân máy tính tự khởi động !
  => Diệt virus Autorun
  => Bấm dây mạng !
  => Bảo vệ mắt khi sử dụng máy tính !
  => Blog ra đời như thế nào?
  => Bài tập Pascal kiểu bản ghi !
  => Hướng dẫn ôn tập lập trình Pascal căn bản !
  => Cách Diệt Virus
  => Cách gỡ bỏ thủ công Symantec Antivirus an toàn (Phần I)
  => Tổng hợp các lệnh ngoài DOS
  => Cài HIREN BOOTCD vào ổ cứng để cứu hộ
  => Cài windows media player 11 ( không cần active window)
  => Cấu hình mạng ADSL cho người dùng tại nhà
  => Thiết Lập Sevice trong windows XP (giúp máy chạy nhanh hơn)
  => Giới Thiệu Centos
  => Chẩn đoán lỗi của màn hình !
  => Chọn DNS truy cập mạng !
  => Kinh nghiệm phòng chống virus, spyware
  => Trắc nghiệm nghiệp vụ kế toán bằng tiếng Anh !
  => Hướng dẫn chụp hình bằng webcam
  => Tổng Hợp Code Dùng Trong Việc Tạo BLOG
  => Công dụng của các dịch vụ trong Windows
  => Sử dụng Popcap game mãi mãi !
  => Cử nhân CNTT không làm CNTT
  => Tìm hiểu DNS.Các bước thiết lập khi mới đăng ký tên miền
  => Làm DNS server online
  => Nội dung định nghĩa về vật chất của Lê Nin
  => Đọc và ... suy nghĩ !
  => Đôi điều về bảo mật hệ thống mạng trong công ty!
  => Khắc phục lỗi 999 Error của Yahoo
  => Chuyển dữ liệu của ổ C từ FAT32 thành NTFS
  => Gỡ password CMOS bằng cách nào?
  => Phần I: Cơ bản về lỗi "màn hình xanh" trong Windows
  => Tổng quan về Group Policy - từ đơn giản đến phức tạp !
  => Gửi nhiều file qua Yahoo Mail
  => Từ XP cài Hacao Linux 2.16 Pro (file ISO) vào đĩa cứng (LiveCD)
  => Chịu thuế và không chịu thuế
  => Hội thảo qua mạng với NetMeeting
  => HOST Free
  => Hướng dẫn download trên megaupload
  => KGB nén File từ 450MB còn 1.43MB rất tiện chia sẻ file trên mạng
  => Khắc phục rớt mạng liên tục
  => Kiến trúc Oracle
  => Thành công trên giảng đường đại học
  => Kỹ thuật Photoshop cơ bản !
  => Kinh nghiệm học tiếng ANH
  => KInh nghiệm học TOÁN CAO CẤP
  => Đôi điều về quá trình làm luận văn (Phần 2)
  => Làm theme cho Blog 360
  => Chia sẻ những điều học được từ cách làm việc theo nhóm
  => Vạch kế hoạch cho tương lai
  => Các Lệnh Cơ Bản trong LINUX
  => Lịch sử các nước ĐẾ QUỐC
  => Lịch sử Việt Nam
  => Links những trang web hay
  => Tạo mail server online bằng IP Động
  => Tự làm giao diện cho Yahoo Mash!
  => Mấy điểm cần tránh
  => Hỏi về IPHONE
  => Máy tính không khởi động từ ổ đĩa cứng!...?
  => MIÊU TẢ SẢN PHẨM MÁY IN hp1320
  => Phá Deep Freeze - Cướp lấy password!!!
  => Những "tuyệt chiêu" chọn mua laptop cũ
  => NHỮNG NGUYÊN TẮC CƠ BẢN CỦA BÁO CHÍ
  => Tìm hiểu nhân của hệ điều hành Linux
  => Sửa lỗi NTLDR is missing
  => Ổ cứng chóng hỏng vì... điều hòa nhiệt độ
  => Những phím tắt thông dụng trong Photoshop 7.0
  => Phím tắt trong WORDS
  => Bí mật của PHỤ NỮ
  => Hướng dẫn post hình lên mạng, và 1 số website để upload hình
  => Chương trình quản lý số điện thoại !
  => Quản lý các mạng Windows dùng script - Phần 2: Hoàn chỉnh script -
  => Cấu hình cho máy in N2500
  => Xóa nick của mình trong Friend List của người khác
  => Rollback Rx Pro:
  => User và pass của một số router
  => Giải pháp sao lưu trực tuyến miễn phí (Phần cuối)
  => Vài điều về Scanner
  => Chọn hệ điều hành của bạn
  => Làm server online tận dụng đường truyền ADSL
  => Thuật toán - Cấu trúc dữ liệu
  => So sánh Oracle và SQL Server ?
  => Cấu hình các công nghệ bảo vệ mạng Windows XP SP2 trên một máy tính
  => Tổng quan về tiết kiệm điện khi sử dụng máy tính !
  => Phần IV: Xử lý sự cố phần cứng
  => CÁC VẤN ĐỀ VỀ SỨC KHỎE PHỤ NỮ
  => Sử dụng phím tắt với Internet Explorer 7
  => SỰ PHÁT TRIỂN CỦA SINH VẬT
  => Nguồn gốc máng cỏ giáng sinh
  => Sưu tầm câu đố !
  => SVCHOST
  => Phòng chống virus cho mạng máy tính doanh nghiệp: kinh nghiệm thực tế
  => Các lệnh căn bản trong ngôn ngữ html
  => Sức mạnh của card đồ họa !
  => Cách tải Nhạc nét
  => Triết học và tâm sự của các nhà giáo
  => Phát triển chiều cao
  => Tăng tốc toàn bộ máy tính bằng tay
  => Tăng tốc WinXP
  => Chống mất cắp cho laptop với Laptop Alarm
  => Tạo file ghost!
  => Tạo một CSS layout từ một bản thiết kế (Phần 1 đến 8)
  => Tạo nick ảo trong Yahoo Messenger
  => Tết Đoan Ngọ bắt đầu từ giữa trưa
  => Thói quen tốt: Nghĩ vậy mà không phải vậy
  => Thomas Edison & những phát minh vĩ đại -
  => Windows Vista: các thủ thuật nhỏ khi sử dụng
  => Thủ thuật Blog 360
  => Thủ thuật Internet Explorer 7
  => Thủ thuật tăng tốc cho Windows
  => Thủ thuật Visual basic
  => Thủ thuật Yahoo! Messenger
  => Yahoo Messenger
  => Khám phá mạng xã hội Yahoo! Mash
  => Mẹo tìm kiếm
  => Tìm kiếm trong Excel
  => Tóc hợp khuôn mặt
  => Tokyo - Một chuyến đi
  => Mười quy luật then chốt về Bảo mật
  => Tổng hợp tất cả các kỹ thuật vượt tường lửa
  => Trang trí USB
  => Thuật toán - Cấu trúc dữ liệu CRC (Cyclic Redundancy Check)
  => Các Tuyệt kỹ khiến phái nữ phải ngã lòng
  => CÁCH UP ẢNH QUA HOST TẠI DIỄN ĐÀN
  => Quản lý danh sách bạn chat trong Yahoo! Messenger
  => Error Doctor 2007
  => TuneUp Utilities® 2007
  => Bộ gõ tiếng Việt: Unikey
  => Hướng dẫn viết bài
  => Tường lửa mới trong Windows Vista và Windows Server Longhorn
  => Web 2.0 không chỉ là công nghệ
  => Các website hữu ích về du học bậc sau đại học tại Hoa Kỳ
  => Wi-fi và an toàn thông tin
  => Thuật toán - Cấu trúc dữ liệu So khớp chuỗi với các ký tự wildcard
  => Xóa địa chỉ và homepage
  => USB không cho ghi
  => Yêu cầu của Quản trị mạng
  => Cách Add Feed trong Blog 360
  => Cách tạo theme trong suốt
  => Đề cương KT-Chính Trị
  Contact
  Guestbook
  Story
  Kiếm tiền thật dễ dàng

Biển xanh ... cát trắng

 

Thuật toán - Cấu trúc dữ liệu
So khớp chuỗi với các ký tự wildcard
Đinh Nguyễn Anh Dũng
Ý nghĩa của ký tự wildcard
Có hai ký tự wildcard là ? và * . Dấu hỏi (?) đại diện cho một ký tự duy nhất bất kỳ. Dấu sao (*) đại diện cho nhiều ký tự bất kỳ hoặc không có ký tự nào cả.
Bạn hãy quan sát vài ví dụ trong bảng dưới đây:
Mẫu
Chuỗi so sánh
Kết quả
w?ldcard
wildcard
khớp
w?ldcard
waldcard
khớp
w*ldcard
wldcard
khớp (không có ký tự)
w*ldcard
willdcard
khớp (có hai ký tự)
w*ldcard*
wldcards
khớp
Thuật toán
Việc xử lý dấu hỏi khá đơn giản. Nếu không có dấu * trong chuỗi mẫu, ta chỉ cần duyệt lần lượt qua từng cặp ký tự trong chuỗi mẫu và chuỗi cần so sánh. Nếu gặp ký tự ? bên chuỗi mẫu thì ta luôn luôn bỏ qua (coi như cặp ký tự ở hai chuỗi là khớp). Ta chỉ cần lưu ý là hai chuỗi phải có cùng chiều dài.
int Match(char *pattern, char *str)
{
  
int i;
  
int j;
  
for (i=0, j=0;( i<strlen(pattern) ) && ( j <strlen(str)) ;i++,j++)
  {
    
if ( pattern[i] == '?')
      
continue;
    
else if (pattern[i] != str[j])
      
return 0;
  }
  
if ( (i==strlen(pattern)) && (j == strlen(str)) )
    
return 1;
  
else
    
return 0;
}
Bước tiếp theo là xử lý trường hợp dấu *. Vì dấu sao đại diện cho nhiều hoặc không ký tự nào nên việc so khớp có vẻ rắc rối. Tuy nhiên, nếu ta xử lý theo kiểu đệ quy thì vấn đề sẽ dễ hiểu và đơn giản hơn. Mục tiêu của đệ quy là đưa bài toán về một bài toán cùng dạng nhưng độ phức tạp giảm dần cho đến khi đạt đến những bài toán cơ bản, dễ giải quyết.
Việc xử lý dấu * chỉ có nghĩa khi phần đầu của chuỗi mẫu và chuỗi so sánh đã khớp với nhau, nếu không thì ta đã có thể kết luận ngay là không khớp. Do vậy để đơn giản mà không làm mất tính tổng quát, ta có thể giả sử là chuỗi mẫu bắt đầu bằng ký tự *
Như vậy chuỗi mẫu sẽ gồm 2 phần: dấu * và phần còn lại. Chuỗi cần so sánh cũng sẽ có 2 phần tương ứng: ký tự tại vị trí dấu * và phần còn lại.
Có 3 trường hợp sau dẫn đến kết quả là chuỗi mẫu và chuỗi so sánh khớp nhau:
a. Dấu * là ký tự duy nhất của chuỗi mẫu. Đây là trường hợp hiển nhiên.
b. Phần còn lại của chuỗi mẫu khớp với toàn bộ chuỗi so sánh (tính chất dấu * đại diện cho không có ký tự nào)
c. Toàn bộ chuỗi mẫu khớp với phần còn lại của chuỗi so sánh (tính chất dấu * đại diện cho 1 hoặc nhiều ký tự)
Hai trường hợp (b) và (c) sẽ dẫn đến việc thực hiện lại bài toán so khớp giữa chuỗi con của chuỗi mẫu và chuỗi con của chuỗi so sánh. Bạn dễ dàng thấy được tính dừng của phép đệ quy này vì mỗi lần đệ quy ta đều giảm chiều dài của chuỗi mẫu hoặc chuỗi so sánh đi một ký tự.
Nếu cả 3 trường hợp trên đều không thỏa thì chuỗi mẫu và chuỗi so sánh không khớp nhau.
Bây giờ ta chỉ cần sửa lại chương trình ban đầu để đưa lời gọi đệ quy vào là xong

int Match(char *pattern, char *str)
{
  int i;
  int j;
  for (i=0, j=0;( i<strlen(pattern) ) && ( j <strlen(str)) ;i++,j++)
  {
    if ( pattern[i] == '?')
      continue;
    else if (pattern[i] == '*')
    {
      if (i==strlen(pattern)-1) return 1;
      else if (Match(&pattern[i+1], &str[i])) return 1;
      else if (Match(&pattern[i], &str[j+1])) return 1;
      else return 0;
    }
    else if (pattern[i] != str[j])
    return 0;
  }
  if ( (i==strlen(pattern)) && (j == strlen(str)) )
    return 1;
  else
    return 0;
}
 
 
Today, there have been 1 visitors (17 hits) on this page!
=> Do you also want a homepage for free? Then click here! <=
Đến với thành phố biển Vũng Tàu