Question

3.       How many successful and unsuccessful comparisons will by made using brute force string matching in a binary string of 1000 zeros while trying to match the following patters:

a.       1000

b.       0001

c.       00010

Answer 1

a.) 1000

There will be a total of 1000-4+1 = 997 iterations. In each of these iterations, the first comparison would
itself be unsuccessful. Hence, there will be 997*1 = 997 unsuccessful comparisons and there will not be
any successful comparisons. Total comparisons = 997.

b.) 0001

The Search String (0000….000) is of length 1000; the Search Pattern (0001) is of length 4. Hence, there
will be 1000-4+1 = 997 iterations. In each of these iterations, the first 3 comparisons would be successful
and the last comparison will be unsuccessful. Hence, there will be 997*3 = 2991 successful comparisons
and 997*1 = 997 unsuccessful comparisons. Total comparisons = 2991 + 997 = 3988 comparisons.

c.) 00010

There will be a total of 1000-5+1 = 996 iterations In each of these iterations, the first 3 comparisons would be successful and second last will be unsuccessful .There will be 996*3 = 2988 successful comparisons and 996*1 = 996 unsuccessful comparisons. Total comaprisons = 2988 + 996 = 3984 comparisons.