In the brute force approach to string search, how many character comparisons will the algorithm make when searching for "lido" in the string "supercalifragilisticexpialidocious"?

  • $\begingroup$ I would say 33... $\endgroup$ – Nicolas FRANCOIS Mar 25 '17 at 10:31
  • $\begingroup$ How did you calculate the result? $\endgroup$ – Hamideh Mar 25 '17 at 10:35
  • $\begingroup$ First put "lido" under the "s" : one comparison, shift right. "lido" under "u", one comparison, shift right... When "lido" gets under "lifragili", 3 comparisons, $f\ne d$, shift right... Until "lido" under "lidocious", four comparisons, we have a winner... $\endgroup$ – Nicolas FRANCOIS Mar 26 '17 at 22:33
  • $\begingroup$ 7+3(lif)+5+3(lis)+9+4(lido)+2=33 In this case, the algorithm jumps over "if" in "lif" , "is" in "lis" and "ido" in "lido". Am I right? $\endgroup$ – Hamideh Mar 28 '17 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.