Number of sub | Python3 program to find the number of sub - strings of s1 which are anagram of any sub - string of s2 ; This function returns true if contents of arr1 [ ] and arr2 [ ] are same , otherwise false . ; This function search for all permutations of string pat [ ] in string txt [ ] ; countP [ ] : Store count of all characters of pattern countTW [ ] : Store count of current window of text ; Traverse through remaining characters of pattern ; Compare counts of current window of text with counts of pattern [ ] ; cout << pat << " ▁ " << txt << " ▁ " ; ; Add current character to current window ; Remove the first character of previous window ; Check for the last window in text ; Function to return the number of sub - strings of s1 that are anagrams of any sub - string of s2 ; initializing variables ; outer loop for picking starting point ; loop for different length of substrings ; If s2 has any substring which is anagram of s1 . substr ( i , len ) ; increment the count ; Driver Code
ALL_CHARS = 256 NEW_LINE def compare ( arr1 , arr2 ) : NEW_LINE INDENT for i in range ( ALL_CHARS ) : NEW_LINE INDENT if arr1 [ i ] != arr2 [ i ] : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def search ( pat , txt ) : NEW_LINE INDENT M = len ( pat ) NEW_LINE N = len ( txt ) NEW_LINE countP = [ 0 ] * ALL_CHARS NEW_LINE countTW = [ 0 ] * ALL_CHARS NEW_LINE for i in range ( M ) : NEW_LINE INDENT countP [ ord ( pat [ i ] ) ] += 1 NEW_LINE countTW [ ord ( txt [ i ] ) ] += 1 NEW_LINE DEDENT for i in range ( M , N ) : NEW_LINE INDENT if compare ( countP , countTW ) : NEW_LINE INDENT return True NEW_LINE DEDENT countTW [ ord ( txt [ i ] ) ] += 1 NEW_LINE countTW [ ord ( txt [ i - M ] ) ] -= 1 NEW_LINE DEDENT if compare ( countP , countTW ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def calculateSubString ( s1 , s2 , n ) : NEW_LINE INDENT count , j , x = 0 , 0 , 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for length in range ( 1 , n - i + 1 ) : NEW_LINE INDENT if search ( s1 [ i : i + length ] , s2 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str1 = " PLEASEHELPIMTRAPPED " NEW_LINE str2 = " INAKICKSTARTFACTORY " NEW_LINE length = len ( str1 ) NEW_LINE print ( calculateSubString ( str1 , str2 , length ) ) NEW_LINE DEDENT