3 int calculate_actual_match(char **text
, char **pattern
, int m
, int n
, int x
, int y
)
5 unsigned int i
= 0, k
, j
, l
, hit
= 0;
7 for( l
= y
; l
< m
+ y
; l
++, i
++ ) {
11 for( j
= x
; j
< m
+ x
; j
++, k
++ )
12 if( pattern
[i
][k
] == text
[l
][j
] )
20 unsigned int karp(char **text
, char **pattern
, int m
, int n
)
22 unsigned int i
, j
, start
= m
;
28 unsigned int row
, matches
= 0;
30 double pattern_hash
= 0, text_hash
= 0;
32 double vertical_pattern
, vertical_text
, vertical_previous_text
;
34 /*Compute the hash for the pattern*/
35 for( i
= 0; i
< m
; i
++ ) {
41 /*Sum all characters in the same row*/
43 for( j
= 0; j
< m
; j
++ )
44 vertical_pattern
+= pattern
[j
][i
];
46 pattern_hash
= pattern_hash
* B
+ vertical_pattern
;
49 /*Compute the hash for the first m elements of the first row of the text*/
51 for( i
= 0; i
< m
; i
++ ) {
55 /*Sum all characters in the same row*/
56 for( j
= 0; j
< m
; j
++ )
57 vertical_text
= vertical_text
+ text
[j
][i
];
59 text_hash
= text_hash
* B
+ vertical_text
;
62 /*Compute the hash for the rest of the text*/
63 for( row
= 0; row
< n
- m
+ 1; row
++ ) {
65 /* On the first row start from the mth character */
69 for( i
= start
; i
< n
; i
++ ) {
71 /*Check if the hashes actually match*/
72 if( pattern_hash
== text_hash
&& calculate_actual_match( text
, pattern
, m
, n
, i
- m
, row
))
75 /* Update text's hash*/
77 vertical_previous_text
= 0;
79 for( j
= 0 + row
; j
< m
+ row
; j
++ ) {
80 vertical_previous_text
= vertical_previous_text
+ text
[j
][i
-m
];
81 vertical_text
= vertical_text
+ text
[j
][i
];
84 text_hash
= ( text_hash
* B
) - ( vertical_previous_text
* Bm
) + vertical_text
;