3 void heur1( int m
, unsigned int *CharJump
)
7 for ( i
= 0; i
< m
; i
++ )
8 CharJump
[i
] = m
- i
-1;
11 void heur2( double *pattern2
, int m
, int n
, unsigned int *MatchJump
, unsigned int *BackUp
)
13 unsigned int i
, ia
, ib
;
15 for ( i
= 1; i
< m
; i
++ )
16 MatchJump
[i
] = 2 * m
- i
;
25 while ( ia
<= m
&& pattern2
[i
- 1] != pattern2
[i
-1] ) {
27 if ( MatchJump
[ia
] > m
- i
)
28 MatchJump
[ia
] = m
- i
;
35 for ( i
= 1; i
< ia
; i
++) {
37 if ( MatchJump
[i
] > m
+ ia
- i
)
38 MatchJump
[i
] = m
+ ia
- i
;
46 if ( MatchJump
[ia
] > ib
- ia
+ m
)
47 MatchJump
[ia
] = ib
- ia
+ m
;
54 int jump( double *text2
, double *pattern2
, int m
, int mark
, unsigned int *CharJump
)
58 for ( i
= 0; i
< m
; i
++ )
59 if( text2
[mark
] == pattern2
[i
] )
64 unsigned int search_bm( double *text2
, double *pattern2
, int m
, int n
)
67 #define max(a,b) ((a) > (b) ? (a) : (b))
70 unsigned int *CharJump
= ( unsigned int* ) malloc( m
* sizeof( unsigned int* ));
72 if( CharJump
== NULL
) {
73 printf("Failed to allocate array!\n");
77 unsigned int *BackUp
= ( unsigned int* ) malloc( n
* sizeof( unsigned int* ));
79 if( BackUp
== NULL
) {
80 printf("Failed to allocate array!\n");
84 unsigned int *MatchJump
= ( unsigned int* ) malloc ( 2 * sizeof ( unsigned int* ) * ( m
+ 1 ) );
86 if( MatchJump
== NULL
) {
87 printf("Failed to allocate array!\n");
91 unsigned int matches
= 0;
95 unsigned int pattern_marker
, text_marker
;
101 /* bm uses two heuristics */
102 heur1( m
, CharJump
);
104 heur2( pattern2
, m
, n
, MatchJump
, BackUp
);
106 const int limit
= n
* n
- ( n
* ( m
- 1 ) );
108 while ( text_marker
< limit
)
110 /* We have a partial match */
111 if ( text2
[text_marker
] == pattern2
[pattern_marker
-1] ) {
117 ia
= jump( text2
, pattern2
, m
, text_marker
, CharJump
);
118 ib
= MatchJump
[pattern_marker
];
119 text_marker
+= max( ia
, ib
);
123 /* We have a match */
124 if ( pattern_marker
== 0 ) {
126 text_marker
+= m
+ 1;