# Derive the formula (n-m+1) number of comparisons for worst case Brute-force string matching algorithm

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:

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

• Please show us where are you stuck. This is a pretty standard problem with tons of explanation all over the internet. Sep 21, 2022 at 4:01
• What is the number of substrings of length $m$ in a string of length $n$? Sep 21, 2022 at 6:52
• @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?". Sep 22, 2022 at 1:03
• @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)! Sep 22, 2022 at 1:38
• @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! Sep 22, 2022 at 1:40