|
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;
}
|
