Finite Automata algorithm for Pattern Searching | Python program for Finite Automata Pattern searching Algorithm ; If the character c is same as next character in pattern , then simply increment state ; Start from the largest possible value and stop when you find a prefix which is also suffix ; This function builds the TF table which represents Finite Automata for a given pattern ; Prints all occurrences of pat in txt ; Process txt over FA . ; Driver program to test above function
NO_OF_CHARS = 256 NEW_LINE def getNextState ( pat , M , state , x ) : NEW_LINE INDENT if state < M and x == ord ( pat [ state ] ) : NEW_LINE INDENT return state + 1 NEW_LINE DEDENT i = 0 NEW_LINE for ns in range ( state , 0 , - 1 ) : NEW_LINE INDENT if ord ( pat [ ns - 1 ] ) == x : NEW_LINE INDENT while ( i < ns - 1 ) : NEW_LINE INDENT if pat [ i ] != pat [ state - ns + 1 + i ] : NEW_LINE INDENT break NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if i == ns - 1 : NEW_LINE INDENT return ns NEW_LINE DEDENT DEDENT DEDENT return 0 NEW_LINE DEDENT def computeTF ( pat , M ) : NEW_LINE INDENT global NO_OF_CHARS NEW_LINE TF = [ [ 0 for i in range ( NO_OF_CHARS ) ] \ for _ in range ( M + 1 ) ] NEW_LINE for state in range ( M + 1 ) : NEW_LINE INDENT for x in range ( NO_OF_CHARS ) : NEW_LINE INDENT z = getNextState ( pat , M , state , x ) NEW_LINE TF [ state ] [ x ] = z NEW_LINE DEDENT DEDENT return TF NEW_LINE DEDENT def search ( pat , txt ) : NEW_LINE INDENT global NO_OF_CHARS NEW_LINE M = len ( pat ) NEW_LINE N = len ( txt ) NEW_LINE TF = computeTF ( pat , M ) NEW_LINE state = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT state = TF [ state ] [ ord ( txt [ i ] ) ] NEW_LINE if state == M : NEW_LINE INDENT print ( " Pattern ▁ found ▁ at ▁ index : ▁ { } " . format ( i - M + 1 ) ) NEW_LINE DEDENT DEDENT DEDENT def main ( ) : NEW_LINE INDENT txt = " AABAACAADAABAAABAA " NEW_LINE pat = " AABA " NEW_LINE search ( pat , txt ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT main ( ) NEW_LINE DEDENT