Anagram Substring Search ( Or Search for all permutations ) | Python program to search all anagrams of a pattern in a text ; This function returns true if contents of arr1 [ ] and arr2 [ ] are same , otherwise false . ; This function search for all permutations of pat [ ] in 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 [ ] ; Add current character to current window ; Remove the first character of previous window ; Check for the last window in text ; Driver program to test above function
MAX = 256 NEW_LINE def compare ( arr1 , arr2 ) : NEW_LINE INDENT for i in range ( MAX ) : 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 ] * MAX NEW_LINE countTW = [ 0 ] * MAX 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 print ( " Found ▁ at ▁ Index " , ( i - M ) ) 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 print ( " Found ▁ at ▁ Index " , N - M ) NEW_LINE DEDENT DEDENT txt = " BACDGABCDA " NEW_LINE pat = " ABCD " NEW_LINE search ( pat , txt ) NEW_LINE