title: Find the number of substrings of a string which can be divisible by a number k
body: <p>given a string, I want to find all the sub-strings which can be formed from the original string which are divisible by an integer k. For example the string 14917 can form 7 sub-strings which are divisible by the integer 7. The sub-strings are: 14, 1491, 14917, 49, 91, 917 and 7. I have come up with a solution but it does not run efficiently when a large string is inputted. My code is</p>
  
  <pre><code>string = '14917'
  divider = 7
  
  count = 0
  for i in range(len(string)):
      for j in range(i+1, len(string)+1):
          sub_string = string[i:j]
          if int(sub_string) % divider == 0:
              count += 1
  
  print(count) 
  </code></pre>
  
  <p>I have read about fast approaches for this kind of a problem, most of which talked about computing the rolling remainders of the string but I could not really implement it correctly. Is there any way in which this problem can be solved quickly. Thanks in advance.</p>