Youtube.com/PoppinKhiem
H C VI N CÔNG NGH B U CHÍNH VI N Ọ Ệ Ệ Ư Ễ THÔNG
KHOA CÔNG NGH THÔNG TIN 1Ệ
BÁO CÁO
MÔN: CHUYÊN Đ CÔNG NGH PH N M MỀ Ệ Ầ Ề
CH Đ: PATTERN SEARCHINGỦ Ề
Gi ng viên: Nguy n Duy Ph ngả ễ ươ
Sinh viên:
Mã SV: B52
Nhóm MH:
1
Youtube.com/PoppinKhiem
Hà N i, 3/7/2021ộ
2
Youtube.com/PoppinKhiem
Muc luc
I. Tim kiêm mâu t trai qua phai ư
1. Thu t toán ậBrute-Force.................................................
2. Thu t toán ậKnuth-Morris-Pratt.....................................
3. Thu t toán ậKarp- Rabin................................................
4. Thu t toán ậMorris-Pratt................................................
5. Thu t toán ậSearch with an automaton..........................
II. Tìm kiêm mâu t phai qua trai ư
1. Thu t toán ậBoyer-Moore..............................................
2. Thu t toán ậTurbo- Boyer- Moore.................................
3. Zhu-Takaota..................................................................
4. Thu t toán ậBerry- Ravindran .......................................
5. Thu t toán ậApostollico- giancarlo................................
6. Thu t toán ậColussi........................................................
III. Tim kiêm mâu t vi tri cu thê ư
1. Thu t toán ậSkip- Search...............................................
2. Thu t toán ậGalil-Giancarlo...........................................
IV. Tim kiê m mâu t vi tri bât ki ư
1. Thu t toán ậQuick Search..............................................
2. Thu t toán ậSmith..........................................................
3. Thu t toán ậRaita............................................................
4. Thu t toán ậHorsePool...................................................
3
Youtube.com/PoppinKhiem
I. Tìm ki m m u t trái qua ph iế ẫ ừ ả
1. Thu t toán Brute Forceậ
Đc đi mặ ể
Không có giai đo n ti n x lýạ ề ử
B nh c n dùng c đnh ộ ớ ầ ố ị
Luôn luôn d ch 1 b c sang ph i ị ướ ả
Vi c so sánh có th ph i dùng trong các tr ng h p ệ ể ả ườ ợ
Đ ph c t p pha th c thi là O(m x n)ộ ứ ạ ự
So sánh kho ng 2n ký tả ự
Trình bày thu t toánậ
Thu t toán Brute Force ki m traậ ể ởt t c các v trí trong đo n văn b n ấ ả ị ạ ả
gi a 0 và n-m, không c n quan tâm li u m u này có t n t i v trí đó ữ ầ ệ ẫ ồ ạ ở ị
hay không. Sau đó, sau m i l n ki m tra m u s d ch sang ph i m t v ỗ ầ ể ẫ ẽ ị ả ộ ị
trí.
Thu t toán Brute Force không c n giai đo n ti n x lý cũng nhậ ầ ạ ề ử ư
các m ng ph cho quá trình tìm ki m. Đ ph c t p tính toán c a thu tả ụ ế ộ ứ ạ ủ ậ
toán này là O(m.n).
Code
void BruteForce(char *x,int m,char *y,int n){
for(int i=0 ; i<=n-m ; i++){
for(int j=0 ; j<m && x[j]==y[j+i] ; j++){ // Kiểm tra t iạ j trong X
có = i+j trong Y
if(j==m-1){
printf("FOUND AT %i \n",i);
}
}
4
Youtube.com/PoppinKhiem
}
}
Ki m nghi m thu t toánể ệ ậ
Xâu X=”AB”
Xâu Y=”ABDAAB”
1YA B D A A B
XA (1) B (2)
2YA B D A A B
XA B
3YA B D A A B
XA
4YA B D A A B
XA (1) B
5YA B D A A B
XA (1) B (2)
2. Thu t toán ậKnuth-Morris-Pratt
Đc đi mặ ể
Th c hi n t trái qua ph iự ệ ừ ả
Pha ti n x lý PreKMP có đ ph c t p không gian và th i gian làề ử ộ ứ ạ ờ
O(m)
Pha tìm ki m có đ ph c t p th i gian O(m+n)ế ộ ứ ạ ờ
Trình bày thu t toánậ
Thu t toán là b n đn gi n và x lý t ng t nh thu t toán ậ ả ơ ả ử ươ ự ư ậ
Morris-Pratt khi c g ng d ch chuy n m t đo n dài nh t sao cho m t ố ắ ị ể ộ ạ ấ ộ
ti n t (prefix) ề ố v c a x trùng v i h u t (suffix) c a uủ ớ ậ ố ủ
Đi m khác nhau là KMP s th c hi n thêm so sánh ể ẽ ự ệ c và b, có
nghĩa KMP s th c hi n m t pha dòm tr c ký t bên ph i đo n đangẽ ự ệ ộ ướ ự ả ạ
5