Finite Automata algorithm for Pattern Searching | Javascript program for Finite Automata Pattern searching Algorithm ; If the character c is same as next character in pattern , then simply increment state ; ns stores the result which is next 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 code
let NO_OF_CHARS = 256 ; function getNextState ( pat , M , state , x ) { if ( state < M && x == pat [ state ] . charCodeAt ( 0 ) ) return state + 1 ; let ns , i ; for ( ns = state ; ns > 0 ; ns -- ) { if ( pat [ ns - 1 ] . charCodeAt ( 0 ) == x ) { for ( i = 0 ; i < ns - 1 ; i ++ ) if ( pat [ i ] != pat [ state - ns + 1 + i ] ) break ; if ( i == ns - 1 ) return ns ; } } return 0 ; } function computeTF ( pat , M , TF ) { let state , x ; for ( state = 0 ; state <= M ; ++ state ) for ( x = 0 ; x < NO_OF_CHARS ; ++ x ) TF [ state ] [ x ] = getNextState ( pat , M , state , x ) ; } function search ( pat , txt ) { let M = pat . length ; let N = txt . length ; let TF = new Array ( M + 1 ) ; for ( let i = 0 ; i < M + 1 ; i ++ ) { TF [ i ] = new Array ( NO_OF_CHARS ) ; for ( let j = 0 ; j < NO_OF_CHARS ; j ++ ) TF [ i ] [ j ] = 0 ; } computeTF ( pat , M , TF ) ; let i , state = 0 ; for ( i = 0 ; i < N ; i ++ ) { state = TF [ state ] [ txt [ i ] . charCodeAt ( 0 ) ] ; if ( state == M ) document . write ( " " + " " + ( i - M + 1 ) + " " ) ; } } let pat = " " . split ( " " ) ; let txt = " " . split ( " " ) ; search ( txt , pat ) ;