4) Determine the number of character comprasions that will bemade by the brute f

Question

4) Determine the number of character comprasions that will bemade by the brute force algorithm in searching for the patternGANDHI in the text THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED (Assume that the length of the text-it is 47 characterslong-is known before the search starts.) 4) Determine the number of character comprasions that will bemade by the brute force algorithm in searching for the patternGANDHI in the text THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED (Assume that the length of the text-it is 47 characterslong-is known before the search starts.)

Explanation / Answer

GHANDI = 6 characters THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED = 47 characters To find a match, you start by checking to see if a character of thetext matches the first character of the search pattern. You're looking for GHANDI. So check the firstcharacter of the seach text. It's a T, which willnot help you find a match. The next one is H...still no good. We've made two character comparisons so far. Therest is pretty boring. There is no G to match inthe search text! We will end up skipping every letter. However, if the algorithm is smart, it won't bother checking thelast 5 characters (SPEED). Because you can't find any6-character string in the last 5 characters of another. So, we will check the length of the text minus the length of thepattern less one. 47 - (6 - 1) = 42 charcomparisons!

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.