Count of substrings of a string containing another given string as a substring | Set 2 | Function to count the substrings of containing another given as a sub ; Store length of S ; Store length of T ; Store the required count of substrings ; Store the starting index of last occurence of T in S ; Iterate in range [ 0 , n1 - n2 ] ; Check if subfrom i to i + n2 is equal to T ; Check if subfrom i to i + n2 is equal to T ; Mark chk as false and break the loop ; If chk is true ; Add ( i + 1 - last ) * ( n1 - ( i + n2 - 1 ) ) to answer ; Update the last to i + 1 ; Prthe answer ; Driver code ; Function Call
def findOccurrences ( S , T ) : NEW_LINE INDENT n1 = len ( S ) NEW_LINE n2 = len ( T ) NEW_LINE ans = 0 NEW_LINE last = 0 NEW_LINE for i in range ( n1 - n2 + 1 ) : NEW_LINE INDENT chk = True NEW_LINE for j in range ( n2 ) : NEW_LINE INDENT if ( T [ j ] != S [ i + j ] ) : NEW_LINE INDENT chk = False NEW_LINE break NEW_LINE DEDENT DEDENT if ( chk ) : NEW_LINE INDENT ans += ( i + 1 - last ) * ( n1 - ( i + n2 - 1 ) ) NEW_LINE last = i + 1 NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S , T = " dabc " , " ab " NEW_LINE findOccurrences ( S , T ) NEW_LINE DEDENT