0
$\begingroup$

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.

$\endgroup$
5
  • $\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

0

Reset to default

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.