I am trying to understand how (n-m+1) (n being the string and m being the pattern) is derived. As in, how could you determine a formula for the number of comparisons in the worst case of a brute-force string matching algorithm.

Here is a look at (n-m+1) being mathmatically derived (where I'm at), that I found: enter image description here

In the above derivation, I am unable to see where the +1 comes into the equation mathmatically.

  • $\begingroup$ Please show us where are you stuck. This is a pretty standard problem with tons of explanation all over the internet. $\endgroup$
    – Rinkesh P
    Sep 21, 2022 at 4:01
  • $\begingroup$ What is the number of substrings of length $m$ in a string of length $n$? $\endgroup$
    – greybeard
    Sep 21, 2022 at 6:52
  • $\begingroup$ @RinkeshP I updated my question to better show what I mean! I want to see how it is mathmatically derived! I dont doubt that (n-m+1) is the number of comparisons, but I want to understand the WHY. Like you would explaining to someone the classic ""Why do you have to have the -1​ in i <= array.length-1​ in the for loop?". $\endgroup$
    – ZenPyro
    Sep 22, 2022 at 1:03
  • $\begingroup$ @greybeard THANK YOU FOR THAT! I ran with it, then found this question asked on the mathmatics Stack Exchange: link and the answers was exactly what I was looking for (after I explained it my way to the imaginary 10 year-old in my brain, Feynman technique style haha)! $\endgroup$
    – ZenPyro
    Sep 22, 2022 at 1:38
  • $\begingroup$ @RinkeshP & greybeard You both can still answer my question in your own words (now that you have a better asked version of my question in that link), if youd like! Who knows, it could further my understanding of it! $\endgroup$
    – ZenPyro
    Sep 22, 2022 at 1:40


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.