SIVERSITY ScIE\CE TECH\OLoGY Brute force算法伪代码2 CHINA Char text[, pat Int n, m int i,], k, lil m lim =n-m+1 for(i=1; i<=lim; 1++) /*search */ for (=l; j<=m & text k==pat[]: j++)k++ if (>m) Report match at position(i-j+1) 021/2 &T
2021/2/4 Department of Computer Science & Technology 11 Brute Force算法伪代码2 Char text[], pat[] ; int n, m ; { int i, j, k, lim ; lim = n-m+1 ; for (i=1 ; i <= lim ; i++) /* search */ { k=i ; for (j=1 ; j<=m && text[k]==pat[j]; j++) k++; if (j>m) Report_match_at_position(i-j+1); } }
Brute forced匹配实例 CHINE Search Text nn e n e d en e n ee d le d SESESE Search Pattern S( Se Search Pattern rn nBdd画過皿妞過函d画e P2/4
2021/2/4 12 Brute Force串匹配实例 n n e e n l Search Text e d e n e e n e e d l e n l d n e e d l e Search Pattern n e e d l e Search Pattern n e d l e Search Pattern n e e d l e Search Pattern n e e d l e Search Pattern n e e d l e Search Pattern n e e d l e Search Pattern n e e d l e Search Pattern n e d l e Search Pattern n e e d l e Search Pattern n e e d l e Search Pattern n e e d l e Search Pattern n e e d l e Search Pattern
(OHNSGIRNGE&(OC Brute force串匹配实例 CHINE Search Text n nee e deneene e d l e n l d Search Pattern n ee d le Search Text n neenee ne e d nn e l e n l d Search Search Searl Search Pa Search Pattern Pattern n Bed dBedBededneeddedne 超出右端边界,停止! P2/4
2021/2/4 13 Brute Force串匹配实例 n n e e n l Search Text e d e n e e n e e d l e n l d n e e d l e Search Pattern n n e e n e Search Text e n e n e e d n n e l e n l d n e e d n e Search Pattern n e e d n e Search Pattern n e d n e Search Pattern n e d n e Search Pattern n e e d n e Search Pattern n e e d n e Search Pattern n e e d n e Search Pattern 超出右端边界，停止！ n e e d n e Search Pattern
SIVERSITY ScIE\CE TECH\OLoGY Brute force算法分析 Anal ysis of brute force Running time depends on pattern and text can be slow when strings repeat themselves Worst case: mN comparisons Search Pattern too slow when m and n are large aaaa ab Search Text aaaaaaa al aaa ala aaaaaa ab aa aa aa aaa aaaa ab ●● 021/2 &T
2021/2/4 Department of Computer Science & Technology 14 Brute Force算法分析 ◼ Analysis of brute force. ◼ Running time depends on pattern and text. ◼ can be slow when strings repeat themselves ◼ Worst case: MN comparisons. ◼ too slow when M and N are large a a a a a b Search Pattern a a a a a a Search Text a a a a a a a a a a a a a a b a a a a a b a a a a a b a a a a a b a a a a a b a a a a a b
SIVERSITY CIE\CE TECH\OLOGY How To Save comparisons How to avoid recomputation? Pre-analyze search pattern Ex: suppose that first 5 characters of pattern are all a's If T[1.5]matches P[1.5]then T[2.5]matches P[1. 4 no need to check i=2,j=1, 2, 3, 4 saves 4 comparisons Need better ideas in general Search Pattern aa aa Search Text aaaaaaaaaaaaaaaaaa b b ●● 021/2 &T
2021/2/4 Department of Computer Science & Technology 15 How To Save Comparisons ◼ How to avoid recomputation? ◼ Pre-analyze search pattern. ◼ Ex: suppose that first 5 characters of pattern are all a's. ◼ If T[1..5] matches P[1..5] then T[2..5] matches P[1..4]. ◼ no need to check i = 2, j = 1, 2, 3, 4 ◼ saves 4 comparisons ◼ Need better ideas in general. a a a a a b Search Pattern a a a a a a Search Text a a a a a a a a a a a a a a b a a a a a b a a a a a b